Add support for test timeouts

10 files changed, 511 insertions, 24 deletions

diff --git a/libbuild2/test/common.cxx b/libbuild2/test/common.cxx
index f50d289..7fdb347 100644
--- a/libbuild2/test/common.cxx
+++ b/libbuild2/test/common.cxx
@@ -6,6 +6,10 @@
 #include <libbuild2/target.hxx>
 #include <libbuild2/algorithm.hxx>
 
+#include <libbuild2/script/timeout.hxx>
+
+#include <libbuild2/test/module.hxx>
+
 using namespace std;
 
 namespace build2
@@ -215,5 +219,73 @@ namespace build2
 
       return r;
     }
+
+    optional<timestamp> common::
+    operation_deadline () const
+    {
+      if (!operation_timeout)
+        return nullopt;
+
+      duration::rep r (operation_deadline_.load (memory_order_consume));
+
+      if (r == timestamp_unknown_rep)
+      {
+        duration::rep t (timestamp (system_clock::now () + *operation_timeout).
+                         time_since_epoch ().count ());
+
+        if (operation_deadline_.compare_exchange_strong (r,
+                                                         t,
+                                                         memory_order_release,
+                                                         memory_order_consume))
+          r = t;
+      }
+
+      return timestamp (duration (r));
+    }
+
+    // Helpers.
+    //
+    optional<timestamp>
+    operation_deadline (const target& t)
+    {
+      optional<timestamp> r;
+
+      for (const scope* s (t.base_scope ().root_scope ());
+           s != nullptr;
+           s = s->parent_scope ()->root_scope ())
+      {
+        if (auto* m = s->find_module<module> (module::name))
+          r = earlier (r, m->operation_deadline ());
+      }
+
+      return r;
+    }
+
+    optional<duration>
+    test_timeout (const target& t)
+    {
+      optional<duration> r;
+
+      for (const scope* s (t.base_scope ().root_scope ());
+           s != nullptr;
+           s = s->parent_scope ()->root_scope ())
+      {
+        if (auto* m = s->find_module<module> (module::name))
+          r = earlier (r, m->test_timeout);
+      }
+
+      return r;
+    }
+
+    optional<timestamp>
+    test_deadline (const target& t)
+    {
+      optional<timestamp> r (operation_deadline (t));
+
+      if (optional<duration> d = test_timeout (t))
+        r = earlier (r, system_clock::now () + *d);
+
+      return r;
+    }
   }
 }
diff --git a/libbuild2/test/common.hxx b/libbuild2/test/common.hxx
index 01628fd..a43b2b1 100644
--- a/libbuild2/test/common.hxx
+++ b/libbuild2/test/common.hxx
@@ -20,6 +20,7 @@ namespace build2
     {
       const variable& config_test;
       const variable& config_test_output;
+      const variable& config_test_timeout;
 
       const variable& var_test;
       const variable& test_options;
@@ -40,11 +41,28 @@ namespace build2
       output_before before = output_before::warn;
       output_after after = output_after::clean;
 
+      // The config.test.timeout values.
+      //
+      optional<duration> operation_timeout;
+      optional<duration> test_timeout;
+
       // The config.test query interface.
       //
       const names* test_ = nullptr; // The config.test value if any.
       scope*       root_ = nullptr; // The root scope for target resolution.
 
+      // Store it as the underlying representation and use the release-consume
+      // ordering (see mtime_target for the reasoning).
+      //
+      mutable atomic<timestamp::rep> operation_deadline_ {
+        timestamp_unknown_rep};
+
+      // Return the test operation deadline, calculating it on the first call
+      // as an offset from now by the operation timeout.
+      //
+      optional<timestamp>
+      operation_deadline () const;
+
       // Return true if the specified alias target should pass-through to its
       // prerequisites.
       //
@@ -65,6 +83,27 @@ namespace build2
       explicit
       common (common_data&& d): common_data (move (d)) {}
     };
+
+    // Helpers.
+    //
+
+    // Return the nearest of the target-enclosing root scopes test operation
+    // deadlines.
+    //
+    optional<timestamp>
+    operation_deadline (const target&);
+
+    // Return the lesser of the target-enclosing root scopes test timeouts.
+    //
+    optional<duration>
+    test_timeout (const target&);
+
+    // Convert the test timeouts in the target-enclosing root scopes into
+    // deadlines and return the nearest between them and the operation
+    // deadlines in the enclosing root scopes.
+    //
+    optional<timestamp>
+    test_deadline (const target&);
   }
 }
 
diff --git a/libbuild2/test/init.cxx b/libbuild2/test/init.cxx
index aaacdc6..0a47842 100644
--- a/libbuild2/test/init.cxx
+++ b/libbuild2/test/init.cxx
@@ -10,6 +10,8 @@
 
 #include <libbuild2/config/utility.hxx>
 
+#include <libbuild2/script/timeout.hxx>
+
 #include <libbuild2/test/module.hxx>
 #include <libbuild2/test/target.hxx>
 #include <libbuild2/test/operation.hxx>
@@ -44,8 +46,8 @@ namespace build2
         //
         // Specified as <target>@<path-id> pairs with both sides being
         // optional. The variable is untyped (we want a list of name-pairs),
-        // overridable, and with global visibiility. The target is relative
-        // (in essence a prerequisite) which is resolved from the (root) scope
+        // overridable, and with global visibility. The target is relative (in
+        // essence a prerequisite) which is resolved from the (root) scope
         // where the config.test value is defined.
         //
         vp.insert ("config.test"),
@@ -55,6 +57,11 @@ namespace build2
         //
         vp.insert<name_pair> ("config.test.output"),
 
+        // Test operation and individual test execution timeouts (see the
+        // manual for semantics).
+        //
+        vp.insert<string> ("config.test.timeout"),
+
         // The test variable is a name which can be a path (with the
         // true/false special values) or a target name.
         //
@@ -189,6 +196,33 @@ namespace build2
         else fail << "invalid config.test.output before value '" << b << "'";
       }
 
+      // config.test.timeout
+      //
+      if (lookup l = lookup_config (rs, m.config_test_timeout))
+      {
+        const string& t (cast<string> (l));
+
+        const char* ot ("config.test.timeout test operation timeout value");
+        const char* tt ("config.test.timeout test timeout value");
+
+        size_t p (t.find ('/'));
+        if (p != string::npos)
+        {
+          // Note: either of the timeouts can be omitted but not both.
+          //
+          if (t.size () == 1)
+            fail << "invalid config.test.timeout value '" << t << "'";
+
+          if (p != 0)
+            m.operation_timeout = parse_timeout (string (t, 0, p), ot);
+
+          if (p != t.size () - 1)
+            m.test_timeout = parse_timeout (string (t, p + 1), tt);
+        }
+        else
+          m.test_timeout = parse_timeout (t, ot);
+      }
+
       //@@ TODO: Need ability to specify extra diff options (e.g.,
       //   --strip-trailing-cr, now hardcoded).
       //
diff --git a/libbuild2/test/module.cxx b/libbuild2/test/module.cxx
new file mode 100644
index 0000000..6b2cbdf
--- /dev/null
+++ b/libbuild2/test/module.cxx
@@ -0,0 +1,12 @@
+// file      : libbuild2/test/module.cxx -*- C++ -*-
+// license   : MIT; see accompanying LICENSE file
+
+#include <libbuild2/test/module.hxx>
+
+namespace build2
+{
+  namespace test
+  {
+    const string module::name ("test");
+  }
+}
diff --git a/libbuild2/test/module.hxx b/libbuild2/test/module.hxx
index 7635f01..c278f5c 100644
--- a/libbuild2/test/module.hxx
+++ b/libbuild2/test/module.hxx
@@ -21,6 +21,8 @@ namespace build2
                    default_rule,
                    group_rule
     {
+      static const string name;
+
       const test::group_rule&
       group_rule () const
       {
diff --git a/libbuild2/test/operation.cxx b/libbuild2/test/operation.cxx
index e9635cf..0a65bed 100644
--- a/libbuild2/test/operation.cxx
+++ b/libbuild2/test/operation.cxx
@@ -3,7 +3,11 @@
 
 #include <libbuild2/test/operation.hxx>
 
+#include <libbuild2/rule.hxx>
 #include <libbuild2/variable.hxx>
+#include <libbuild2/algorithm.hxx>
+
+#include <libbuild2/test/common.hxx> // test_deadline()
 
 using namespace std;
 using namespace butl;
@@ -23,6 +27,36 @@ namespace build2
       return mo != disfigure_id ? update_id : 0;
     }
 
+    // Ad hoc rule apply callback.
+    //
+    // If this is not perform(test) or there is no deadline set for the test
+    // execution, then forward the call to the ad hoc rule's apply().
+    // Otherwise, return a recipe that will execute with the deadline if we
+    // can get it and return the noop recipe that just issues a warning if we
+    // can't.
+    //
+    static recipe
+    adhoc_apply (const adhoc_rule& ar, action a, target& t, match_extra& me)
+    {
+      optional<timestamp> d;
+
+      if (a != perform_test_id || !(d = test_deadline (t)))
+        return ar.apply (a, t, me);
+
+      if (const auto* dr = dynamic_cast<const adhoc_rule_with_deadline*> (&ar))
+      {
+        if (recipe r = dr->apply (a, t, me, d))
+          return r;
+      }
+
+      return [] (action a, const target& t)
+      {
+        warn << "unable to impose timeout on test for target " << t
+             << ", skipping";
+        return noop_action (a, t);
+      };
+    }
+
     const operation_info op_test {
       test_id,
       0,
@@ -36,7 +70,7 @@ namespace build2
       &test_pre,
       nullptr,
       nullptr,
-      nullptr
+      &adhoc_apply
     };
 
     // Also the explicit update-for-test operation alias.
diff --git a/libbuild2/test/rule.cxx b/libbuild2/test/rule.cxx
index db490d9..df2d5ba 100644
--- a/libbuild2/test/rule.cxx
+++ b/libbuild2/test/rule.cxx
@@ -3,6 +3,12 @@
 
 #include <libbuild2/test/rule.hxx>
 
+#ifndef _WIN32
+#  include <signal.h>                  // SIG*
+#else
+#  include <libbutl/win32-utility.hxx> // DBG_TERMINATE_PROCESS
+#endif
+
 #include <libbuild2/scope.hxx>
 #include <libbuild2/target.hxx>
 #include <libbuild2/context.hxx>
@@ -632,11 +638,30 @@ namespace build2
     // ...
     // nameN arg arg ... nullptr nullptr
     //
+    // Stack-allocated linked list of information about the running pipeline
+    // processes.
+    //
+    struct pipe_process
+    {
+      process&    proc;
+      const char* prog; // Only for diagnostics.
+
+      // True if this process has been terminated.
+      //
+      bool terminated = false;
+
+      pipe_process* prev; // NULL for the left-most program.
+
+      pipe_process (process& p, const char* g, pipe_process* r)
+          : proc (p), prog (g), prev (r) {}
+    };
+
     static bool
     run_test (const target& t,
               diag_record& dr,
               char const** args,
-              process* prev = nullptr)
+              const optional<timestamp>& deadline,
+              pipe_process* prev = nullptr)
     {
       // Find the next process, if any.
       //
@@ -648,19 +673,116 @@ namespace build2
       //
       int out (*next != nullptr ? -1 : 1);
       bool pr;
-      process_exit pe;
+
+      // Absent if the process misses the deadline.
+      //
+      optional<process_exit> pe;
 
       try
       {
+        // Wait for a process to complete until the deadline is reached and
+        // return the underlying wait function result.
+        //
+        auto timed_wait = [] (process& p, const timestamp& deadline)
+        {
+          timestamp now (system_clock::now ());
+          return deadline > now
+                 ? p.timed_wait (deadline - now)
+                 : p.try_wait ();
+        };
+
+        // Terminate the pipeline processes starting from the specified one
+        // and up to the leftmost one and then kill those which didn't
+        // terminate in 1 second. Issue diagnostics and fail if something goes
+        // wrong, but still try to terminate all processes.
+        //
+        auto term_pipe = [&timed_wait] (pipe_process* pp)
+        {
+          diag_record dr;
+
+          // Terminate processes gracefully and set the terminate flag for
+          // them.
+          //
+          for (pipe_process* p (pp); p != nullptr; p = p->prev)
+          {
+            try
+            {
+              p->proc.term ();
+            }
+            catch (const process_error& e)
+            {
+              dr << fail << "unable to terminate " << p->prog << ": " << e;
+            }
+
+            p->terminated = true;
+          }
+
+          // Wait a bit for the processes to terminate and kill the remaining
+          // ones.
+          //
+          timestamp deadline (system_clock::now () + chrono::seconds (1));
+
+          for (pipe_process* p (pp); p != nullptr; p = p->prev)
+          {
+            process& pr (p->proc);
+
+            try
+            {
+              if (!timed_wait (pr, deadline))
+              {
+                pr.kill ();
+                pr.wait ();
+              }
+            }
+            catch (const process_error& e)
+            {
+              dr << fail << "unable to wait/kill " << p->prog << ": " << e;
+            }
+          }
+        };
+
         process p (prev == nullptr
-                   ? process (args, 0, out)       // First process.
-                   : process (args, *prev, out)); // Next process.
+                   ? process (args, 0, out)            // First process.
+                   : process (args, prev->proc, out)); // Next process.
 
-        pr = *next == nullptr || run_test (t, dr, next, &p);
-        p.wait ();
+        pipe_process pp (p, args[0], prev);
+
+        // If the deadline is specified, then make sure we don't miss it
+        // waiting indefinitely in the process destructor on the right-hand
+        // part of the pipe failure.
+        //
+        auto g (make_exception_guard ([&deadline, &pp, &term_pipe] ()
+        {
+          if (deadline)
+          try
+          {
+            term_pipe (&pp);
+          }
+          catch (const failed&)
+          {
+            // We can't do much here.
+          }
+        }));
+
+        pr = *next == nullptr || run_test (t, dr, next, deadline, &pp);
+
+        if (!deadline)
+          p.wait ();
+        else if (!timed_wait (p, *deadline))
+          term_pipe (&pp);
 
         assert (p.exit);
-        pe = *p.exit;
+
+#ifndef _WIN32
+        if (!(pp.terminated      &&
+              !p.exit->normal () &&
+              p.exit->signal () == SIGTERM))
+#else
+        if (!(pp.terminated &&
+              !p.exit->normal () &&
+              p.exit->status == DBG_TERMINATE_PROCESS))
+#endif
+          pe = *p.exit;
       }
       catch (const process_error& e)
       {
@@ -672,7 +794,7 @@ namespace build2
         throw failed ();
       }
 
-      bool wr (pe.normal () && pe.code () == 0);
+      bool wr (pe && pe->normal () && pe->code () == 0);
 
       if (!wr)
       {
@@ -681,7 +803,11 @@ namespace build2
 
         dr << error;
         print_process (dr, args);
-        dr << " " << pe;
+
+        if (pe)
+          dr << " " << *pe;
+        else
+          dr << " terminated: execution timeout expired";
       }
 
       return pr && wr;
@@ -896,10 +1022,13 @@ namespace build2
       if (!ctx.dry_run)
       {
         diag_record dr;
+        pipe_process pp (cat, "cat", nullptr);
+
         if (!run_test (tt,
                        dr,
                        args.data () + (sin ? 3 : 0), // Skip cat.
-                       sin ? &cat : nullptr))
+                       test_deadline (tt),
+                       sin ? &pp : nullptr))
         {
           dr << info << "test command line: ";
           print_process (dr, args);
diff --git a/libbuild2/test/script/parser+env.test.testscript b/libbuild2/test/script/parser+env.test.testscript
index b1e864c..b6fb305 100644
--- a/libbuild2/test/script/parser+env.test.testscript
+++ b/libbuild2/test/script/parser+env.test.testscript
@@ -48,10 +48,10 @@
 : set
 :
 {
-  $* <'env a=b -- cmd'      >'env a=b -- cmd'        : var
-  $* <'env -u a b=c -- cmd' >'env -u a - b=c -- cmd' : opt-var
-  $* <'env a="b c" -- cmd'  >"env a='b c' -- cmd"    : quote
-  $* <'env "a b"=c -- cmd'  >"env 'a b=c' -- cmd"    : quote-name
+  $* <'env a=b -- cmd'      >'env a=b -- cmd'      : var
+  $* <'env -u a b=c -- cmd' >'env -u a b=c -- cmd' : opt-var
+  $* <'env a="b c" -- cmd'  >"env a='b c' -- cmd"  : quote
+  $* <'env "a b"=c -- cmd'  >"env 'a b=c' -- cmd"  : quote-name
 
   : double-quote
   :
@@ -66,9 +66,19 @@
     EOE
 }
 
+: timeout
+:
+{
+  $* <'env -t 5 -- cmd'        >'env -t 5 -- cmd'      : short-opt
+  $* <'env --timeout 5 -- cmd' >'env -t 5 -- cmd'      : long-opt
+  $* <'env --timeout=5 -- cmd' >'env -t 5 -- cmd'      : long-opt-eq
+  $* <'env -u a -t 5 -- cmd'   >'env -t 5 -u a -- cmd' : mult-opt
+  $* <'env -t 5 a=b -- cmd'    >'env -t 5 a=b -- cmd'  : args
+}
+
 : non-first
 :
-$* <'cmd1 && env -u a b=c -- cmd2' >'cmd1 && env -u a - b=c -- cmd2'
+$* <'cmd1 && env -u a b=c -- cmd2' >'cmd1 && env -u a b=c -- cmd2'
 
 : no-cmd
 :
diff --git a/libbuild2/test/script/script.cxx b/libbuild2/test/script/script.cxx
index 34d4723..3f615ee 100644
--- a/libbuild2/test/script/script.cxx
+++ b/libbuild2/test/script/script.cxx
@@ -8,6 +8,10 @@
 #include <libbuild2/target.hxx>
 #include <libbuild2/algorithm.hxx>
 
+#include <libbuild2/script/timeout.hxx>
+
+#include <libbuild2/test/common.hxx>        // operation_deadline(),
+                                            // test_timeout()
 #include <libbuild2/test/script/parser.hxx>
 
 using namespace std;
@@ -18,6 +22,9 @@ namespace build2
   {
     namespace script
     {
+      using build2::script::to_deadline;
+      using build2::script::to_timeout;
+
       // scope_base
       //
       scope_base::
@@ -188,11 +195,14 @@ namespace build2
       // script
       //
       script::
-      script (const target& tt,
-              const testscript& st,
-              const dir_path& rwd)
+      script (const target& tt, const testscript& st, const dir_path& rwd)
           : script_base (tt, st),
-            group (st.name == "testscript" ? string () : st.name, *this)
+            group (st.name == "testscript" ? string () : st.name, *this),
+            operation_deadline (
+              to_deadline (build2::test::operation_deadline (tt),
+                           false /* success */)),
+            test_timeout (to_timeout (build2::test::test_timeout (tt),
+                                      false /* success */))
       {
         // Set the script working dir ($~) to $out_base/test/<id> (id_path
         // for root is just the id which is empty if st is 'testscript').
@@ -282,6 +292,14 @@ namespace build2
         reset_special ();
       }
 
+      optional<deadline> script::
+      effective_deadline ()
+      {
+        return earlier (operation_deadline, group_deadline);
+      }
+
+      // scope
+      //
       lookup scope::
       lookup (const variable& var) const
       {
@@ -409,6 +427,86 @@ namespace build2
         //
         assign (root.cmd_var) = move (s);
       }
+
+      // group
+      //
+      void group::
+      set_timeout (const string& t, bool success, const location& l)
+      {
+        const char* gt (parent != nullptr
+                        ? "test group timeout"
+                        : "testscript timeout");
+
+        const char* tt ("test timeout");
+
+        size_t p (t.find ('/'));
+        if (p != string::npos)
+        {
+          // Note: either of the timeouts can be omitted but not both.
+          //
+          if (t.size () == 1)
+            fail (l) << "invalid timeout '" << t << "'";
+
+          if (p != 0)
+            group_deadline =
+              to_deadline (parse_deadline (string (t, 0, p), gt, l),
+                           success);
+
+          if (p != t.size () - 1)
+            test_timeout =
+              to_timeout (parse_timeout (string (t, p + 1), tt, l), success);
+        }
+        else
+          group_deadline = to_deadline (parse_deadline (t, gt, l), success);
+      }
+
+      optional<deadline> group::
+      effective_deadline ()
+      {
+        return parent != nullptr
+               ? earlier (parent->effective_deadline (), group_deadline)
+               : group_deadline;
+      }
+
+      // test
+      //
+      void test::
+      set_timeout (const string& t, bool success, const location& l)
+      {
+        fragment_deadline =
+          to_deadline (parse_deadline (t, "test fragment timeout", l),
+                       success);
+      }
+
+      optional<deadline> test::
+      effective_deadline ()
+      {
+        if (!test_deadline)
+        {
+          assert (parent != nullptr); // Test is always inside a group scope.
+
+          test_deadline = parent->effective_deadline ();
+
+          // Calculate the minimum timeout and factor it into the resulting
+          // deadline.
+          //
+          optional<timeout> t (root.test_timeout); // config.test.timeout
+          for (const scope* p (parent); p != nullptr; p = p->parent)
+          {
+            const group* g (dynamic_cast<const group*> (p));
+            assert (g != nullptr);
+
+            t = earlier (t, g->test_timeout);
+          }
+
+          if (t)
+            test_deadline =
+              earlier (*test_deadline,
+                       deadline (system_clock::now () + t->value, t->success));
+        }
+
+        return earlier (*test_deadline, fragment_deadline);
+      }
     }
   }
 }
diff --git a/libbuild2/test/script/script.hxx b/libbuild2/test/script/script.hxx
index 6356501..2789cab 100644
--- a/libbuild2/test/script/script.hxx
+++ b/libbuild2/test/script/script.hxx
@@ -28,6 +28,8 @@ namespace build2
       using build2::script::redirect_type;
       using build2::script::line_type;
       using build2::script::command_expr;
+      using build2::script::deadline;
+      using build2::script::timeout;
 
       class parser; // Required by VC for 'friend class parser' declaration.
 
@@ -168,10 +170,29 @@ namespace build2
       class group: public scope
       {
       public:
-        vector<unique_ptr<scope>> scopes;
+        group (const string& id, group& p): scope (id, &p, p.root) {}
 
       public:
-        group (const string& id, group& p): scope (id, &p, p.root) {}
+        vector<unique_ptr<scope>> scopes;
+
+        // The test group execution deadline and the individual test timeout.
+        //
+        optional<deadline> group_deadline;
+        optional<timeout>  test_timeout;
+
+        // Parse the argument having the '[<group-timeout>]/[<test-timeout>]'
+        // form, where the values are expressed in seconds and either of them
+        // (but not both) can be omitted, and set the group deadline and test
+        // timeout respectively, if specified. Reset them to nullopt on zero.
+        //
+        virtual void
+        set_timeout (const string&, bool success, const location&) override;
+
+        // Return the nearest of the own deadline and the enclosing groups
+        // deadlines.
+        //
+        virtual optional<deadline>
+        effective_deadline () override;
 
       protected:
         group (const string& id, script& r): scope (id, nullptr, r) {}
@@ -207,6 +228,29 @@ namespace build2
       public:
         test (const string& id, group& p): scope (id, &p, p.root) {}
 
+      public:
+        // The whole test and the remaining test fragment execution deadlines.
+        //
+        // The former is based on the minimum of the test timeouts set for the
+        // enclosing scopes and is calculated on the first deadline() call.
+        // The later is set by set_timeout() from the timeout builtin call
+        // during the test execution.
+        //
+        optional<optional<deadline>> test_deadline; // calculated<specified<>>
+        optional<deadline>           fragment_deadline;
+
+        // Parse the specified in seconds timeout and set the remaining test
+        // fragment execution deadline. Reset it to nullopt on zero.
+        //
+        virtual void
+        set_timeout (const string&, bool success, const location&) override;
+
+        // Return the nearest of the test and fragment execution deadlines,
+        // calculating the former on the first call.
+        //
+        virtual optional<deadline>
+        effective_deadline () override;
+
         // Pre-parse data.
         //
       public:
@@ -254,6 +298,13 @@ namespace build2
       class script: public script_base, public group
       {
       public:
+        // The test operation deadline and the individual test timeout (see
+        // the config.test.timeout variable for details).
+        //
+        optional<deadline> operation_deadline;
+        optional<timeout>  test_timeout;
+
+      public:
         script (const target& test_target,
                 const testscript& script_target,
                 const dir_path& root_wd);
@@ -263,6 +314,12 @@ namespace build2
         script& operator= (script&&) = delete;
         script& operator= (const script&) = delete;
 
+        // Return the nearest of the test operation and group execution
+        // deadlines.
+        //
+        virtual optional<deadline>
+        effective_deadline () override;
+
         // Pre-parse data.
         //
       private: