Initial self-hosting commit

This is the initial version of our tool that is able to
build itself. In can be bootstrapped by

  ./bin/bootstrap.py

Co-authored-by: Oliver Reiche <oliver.reiche@huawei.com>
Co-authored-by: Victor Moreno <victor.moreno1@huawei.com>

6 files changed, 1089 insertions, 0 deletions

diff --git a/test/buildtool/multithreading/TARGETS b/test/buildtool/multithreading/TARGETS
new file mode 100644
index 00000000..09fafaa8
--- /dev/null
+++ b/test/buildtool/multithreading/TARGETS
@@ -0,0 +1,76 @@
+{ "task":
+  { "type": ["@", "rules", "CC/test", "test"]
+  , "name": ["task"]
+  , "srcs": ["task.test.cpp"]
+  , "deps":
+    [ ["@", "catch2", "", "catch2"]
+    , ["test", "catch-main"]
+    , ["src/buildtool/multithreading", "task_system"]
+    ]
+  , "stage": ["test", "buildtool", "multithreading"]
+  }
+, "task_system":
+  { "type": ["@", "rules", "CC/test", "test"]
+  , "name": ["task_system"]
+  , "srcs": ["task_system.test.cpp"]
+  , "deps":
+    [ ["@", "catch2", "", "catch2"]
+    , ["test", "catch-main"]
+    , ["test/utils", "container_matchers"]
+    , ["src/buildtool/multithreading", "task_system"]
+    ]
+  , "stage": ["test", "buildtool", "multithreading"]
+  }
+, "async_map_node":
+  { "type": ["@", "rules", "CC/test", "test"]
+  , "name": ["async_map_node"]
+  , "srcs": ["async_map_node.test.cpp"]
+  , "deps":
+    [ ["@", "catch2", "", "catch2"]
+    , ["test", "catch-main"]
+    , ["test/utils", "container_matchers"]
+    , ["src/buildtool/multithreading", "async_map_node"]
+    , ["src/buildtool/multithreading", "task_system"]
+    ]
+  , "stage": ["test", "buildtool", "multithreading"]
+  }
+, "async_map":
+  { "type": ["@", "rules", "CC/test", "test"]
+  , "name": ["async_map"]
+  , "srcs": ["async_map.test.cpp"]
+  , "deps":
+    [ ["@", "catch2", "", "catch2"]
+    , ["test", "catch-main"]
+    , ["test/utils", "container_matchers"]
+    , ["src/buildtool/multithreading", "async_map"]
+    , ["src/buildtool/multithreading", "async_map_node"]
+    , ["src/buildtool/multithreading", "task_system"]
+    ]
+  , "stage": ["test", "buildtool", "multithreading"]
+  }
+, "async_map_consumer":
+  { "type": ["@", "rules", "CC/test", "test"]
+  , "name": ["async_map_consumer"]
+  , "srcs": ["async_map_consumer.test.cpp"]
+  , "deps":
+    [ ["@", "catch2", "", "catch2"]
+    , ["test", "catch-main"]
+    , ["test/utils", "container_matchers"]
+    , ["src/buildtool/multithreading", "async_map_consumer"]
+    , ["src/buildtool/multithreading", "async_map"]
+    , ["src/buildtool/multithreading", "task_system"]
+    ]
+  , "stage": ["test", "buildtool", "multithreading"]
+  }
+, "TESTS":
+  { "type": "install"
+  , "tainted": ["test"]
+  , "deps":
+    [ "async_map"
+    , "async_map_consumer"
+    , "async_map_node"
+    , "task"
+    , "task_system"
+    ]
+  }
+}
\ No newline at end of file
diff --git a/test/buildtool/multithreading/async_map.test.cpp b/test/buildtool/multithreading/async_map.test.cpp
new file mode 100644
index 00000000..bac7f031
--- /dev/null
+++ b/test/buildtool/multithreading/async_map.test.cpp
@@ -0,0 +1,58 @@
+#include <string>
+
+#include "catch2/catch.hpp"
+#include "src/buildtool/multithreading/async_map.hpp"
+#include "src/buildtool/multithreading/async_map_node.hpp"
+#include "src/buildtool/multithreading/task_system.hpp"
+
+TEST_CASE("Single-threaded: nodes only created once", "[async_map]") {
+    AsyncMap<std::string, int> map;
+    auto* key_node = map.GetOrCreateNode("key");
+    CHECK(key_node != nullptr);
+
+    auto* other_node = map.GetOrCreateNode("otherkey");
+    CHECK(other_node != nullptr);
+
+    auto* should_be_key_node = map.GetOrCreateNode("key");
+    CHECK(should_be_key_node != nullptr);
+
+    CHECK(key_node != other_node);
+    CHECK(key_node == should_be_key_node);
+}
+
+TEST_CASE("Nodes only created once and survive the map destruction",
+          "[async_map]") {
+
+    using NodePtr = typename AsyncMap<std::string, int>::NodePtr;
+    NodePtr key_node{nullptr};
+    NodePtr other_node{nullptr};
+    NodePtr should_be_key_node{nullptr};
+    {
+        AsyncMap<std::string, int> map;
+        {
+            TaskSystem ts;
+            ts.QueueTask([&key_node, &map]() {
+                auto* node = map.GetOrCreateNode("key");
+                CHECK(node != nullptr);
+                key_node = node;
+            });
+
+            ts.QueueTask([&other_node, &map]() {
+                auto* node = map.GetOrCreateNode("otherkey");
+                CHECK(node != nullptr);
+                other_node = node;
+            });
+
+            ts.QueueTask([&should_be_key_node, &map]() {
+                auto* node = map.GetOrCreateNode("key");
+                CHECK(node != nullptr);
+                should_be_key_node = node;
+            });
+        }
+    }
+    CHECK(key_node != nullptr);
+    CHECK(other_node != nullptr);
+    CHECK(should_be_key_node != nullptr);
+    CHECK(key_node != other_node);
+    CHECK(key_node == should_be_key_node);
+}
diff --git a/test/buildtool/multithreading/async_map_consumer.test.cpp b/test/buildtool/multithreading/async_map_consumer.test.cpp
new file mode 100644
index 00000000..5edaeec0
--- /dev/null
+++ b/test/buildtool/multithreading/async_map_consumer.test.cpp
@@ -0,0 +1,309 @@
+#include <cstdint>  // for fixed width integral types
+#include <numeric>
+#include <string>
+
+#include "catch2/catch.hpp"
+#include "src/buildtool/multithreading/async_map.hpp"
+#include "src/buildtool/multithreading/async_map_consumer.hpp"
+#include "src/buildtool/multithreading/task_system.hpp"
+
+auto FibonacciMapConsumer() -> AsyncMapConsumer<int, uint64_t> {
+    auto value_creator = [](auto /*unused*/,
+                            auto setter,
+                            auto logger,
+                            auto subcaller,
+                            auto const& key) {
+        if (key < 0) {
+            (*logger)("index needs to be non-negative", true);
+            return;
+        }
+        if (key < 2) {
+            (*setter)(uint64_t{static_cast<uint64_t>(key)});
+            return;
+        }
+        (*subcaller)(
+            std::vector<int>{key - 2, key - 1},
+            [setter](auto const& values) {
+                (*setter)(*values[0] + *values[1]);
+            },
+            logger);
+    };
+    return AsyncMapConsumer<int, uint64_t>{value_creator};
+}
+
+auto FibOnEvenConsumer() -> AsyncMapConsumer<int, uint64_t> {
+    auto value_creator = [](auto /*unused*/,
+                            auto setter,
+                            auto logger,
+                            auto subcaller,
+                            auto const& key) {
+        if (key < 0) {
+            (*logger)("index needs to be non-negative (and actually even)",
+                      true);
+            return;
+        }
+        if (key == 0) {
+            (*setter)(uint64_t{static_cast<uint64_t>(0)});
+            return;
+        }
+        if (key == 2) {
+            (*setter)(uint64_t{static_cast<uint64_t>(1)});
+            return;
+        }
+        (*subcaller)(
+            std::vector<int>{key - 4, key - 2},
+            [setter](auto const& values) {
+                (*setter)(*values[0] + *values[1]);
+            },
+            logger);
+    };
+    return AsyncMapConsumer<int, uint64_t>{value_creator};
+}
+
+auto CountToMaxConsumer(int max_val, int step = 1, bool cycle = false)
+    -> AsyncMapConsumer<int, uint64_t> {
+    auto value_creator = [max_val, step, cycle](auto /*unused*/,
+                                                auto setter,
+                                                auto logger,
+                                                auto subcaller,
+                                                auto const& key) {
+        if (key < 0 or key > max_val) {  // intentional bug: non-fatal abort
+            (*logger)("index out of range", false);
+            return;
+        }
+        if (key == max_val) {  // will never be reached if cycle==true
+            (*setter)(uint64_t{static_cast<uint64_t>(key)});
+            return;
+        }
+        auto next = key + step;
+        if (cycle) {
+            next %= max_val;
+        }
+        (*subcaller)(
+            {next},
+            [setter](auto const& values) { (*setter)(uint64_t{*values[0]}); },
+            logger);
+    };
+    return AsyncMapConsumer<int, uint64_t>{value_creator};
+}
+
+TEST_CASE("Fibonacci", "[async_map_consumer]") {
+    uint64_t result{};
+    int const index{92};
+    bool execution_failed = false;
+    uint64_t const expected_result{7540113804746346429};
+    auto mapconsumer = FibonacciMapConsumer();
+    {
+        TaskSystem ts;
+
+        mapconsumer.ConsumeAfterKeysReady(
+            &ts,
+            {index},
+            [&result](auto const& values) { result = *values[0]; },
+            [&execution_failed](std::string const& /*unused*/,
+                                bool /*unused*/) { execution_failed = true; });
+    }
+    CHECK(not execution_failed);
+    CHECK(result == expected_result);
+}
+
+TEST_CASE("Values only used once nodes are marked ready",
+          "[async_map_consumer]") {
+    AsyncMapConsumer<int, bool> consume_when_ready{[](auto /*unused*/,
+                                                      auto setter,
+                                                      auto logger,
+                                                      auto subcaller,
+                                                      auto const& key) {
+        if (key == 0) {
+            (*setter)(true);
+            return;
+        }
+        (*subcaller)(
+            {key - 1},
+            [setter, logger, key](auto const& values) {
+                auto const ready_when_used = values[0];
+                if (not ready_when_used) {
+                    (*logger)(std::to_string(key), true);
+                }
+                (*setter)(true);
+            },
+            logger);
+    }};
+    std::vector<std::string> value_used_before_ready{};
+    std::mutex vectorm;
+    bool final_value{false};
+    int const starting_index = 100;
+    {
+        TaskSystem ts;
+
+        consume_when_ready.ConsumeAfterKeysReady(
+            &ts,
+            {starting_index},
+            [&final_value](auto const& values) { final_value = values[0]; },
+            [&value_used_before_ready, &vectorm](std::string const& key,
+                                                 bool /*unused*/) {
+                std::unique_lock l{vectorm};
+                value_used_before_ready.push_back(key);
+            });
+    }
+    CHECK(value_used_before_ready.empty());
+    CHECK(final_value);
+}
+
+TEST_CASE("No subcalling necessary", "[async_map_consumer]") {
+    AsyncMapConsumer<int, int> identity{
+        [](auto /*unused*/,
+           auto setter,
+           [[maybe_unused]] auto logger,
+           [[maybe_unused]] auto subcaller,
+           auto const& key) { (*setter)(int{key}); }};
+    std::vector<int> final_values{};
+    std::vector<int> const keys{1, 23, 4};
+    {
+        TaskSystem ts;
+        identity.ConsumeAfterKeysReady(
+            &ts,
+            keys,
+            [&final_values](auto const& values) {
+                std::transform(values.begin(),
+                               values.end(),
+                               std::back_inserter(final_values),
+                               [](auto* val) { return *val; });
+            },
+            [](std::string const& /*unused*/, bool /*unused*/) {});
+    }
+    CHECK(keys == final_values);
+}
+
+TEST_CASE("FibOnEven", "[async_map_consumer]") {
+    uint64_t result{};
+    int const index{184};
+    bool execution_failed = false;
+    uint64_t const expected_result{7540113804746346429};
+    auto mapconsumer = FibOnEvenConsumer();
+    {
+        TaskSystem ts;
+
+        mapconsumer.ConsumeAfterKeysReady(
+            &ts,
+            {index},
+            [&result](auto const& values) { result = *values[0]; },
+            [&execution_failed](std::string const& /*unused*/,
+                                bool /*unused*/) { execution_failed = true; });
+    }
+    CHECK(not execution_failed);
+    CHECK(result == expected_result);
+}
+
+TEST_CASE("ErrorPropagation", "[async_map_consumer]") {
+    int const index{183};  // Odd number, will fail
+    bool execution_failed = false;
+    bool consumer_called = false;
+    std::atomic<int> fail_cont_counter{0};
+    auto mapconsumer = FibOnEvenConsumer();
+    {
+        TaskSystem ts;
+
+        mapconsumer.ConsumeAfterKeysReady(
+            &ts,
+            {index},
+            [&consumer_called](auto const& /*unused*/) {
+                consumer_called = true;
+            },
+            [&execution_failed](std::string const& /*unused*/,
+                                bool /*unused*/) { execution_failed = true; },
+            [&fail_cont_counter]() { fail_cont_counter++; });
+    }
+    CHECK(execution_failed);
+    CHECK(!consumer_called);
+    CHECK(fail_cont_counter == 1);
+}
+
+TEST_CASE("Failure detection", "[async_map_consumer]") {
+    int const kMaxVal = 1000;  // NOLINT
+    std::optional<int> value{std::nullopt};
+    bool failed{};
+
+    SECTION("Unfinished pending keys") {
+        int const kStep{3};
+        REQUIRE(std::lcm(kMaxVal, kStep) > kMaxVal);
+        auto map = CountToMaxConsumer(kMaxVal, kStep);
+        {
+            TaskSystem ts;
+            map.ConsumeAfterKeysReady(
+                &ts,
+                {0},
+                [&value](auto const& values) { value = *values[0]; },
+                [&failed](std::string const& /*unused*/, bool fatal) {
+                    failed = failed or fatal;
+                });
+        }
+        CHECK_FALSE(value);
+        CHECK_FALSE(failed);
+        CHECK_FALSE(map.DetectCycle());
+
+        auto const pending = map.GetPendingKeys();
+        CHECK_FALSE(pending.empty());
+
+        std::vector<int> expected{};
+        expected.reserve(kMaxVal + 1);
+        for (int i = 0; i < kMaxVal + kStep; i += kStep) {
+            expected.emplace_back(i);
+        }
+        CHECK_THAT(pending, Catch::Matchers::UnorderedEquals(expected));
+    }
+
+    SECTION("Cycle containing all unfinished keys") {
+        auto map = CountToMaxConsumer(kMaxVal, 1, /*cycle=*/true);
+        {
+            TaskSystem ts;
+            map.ConsumeAfterKeysReady(
+                &ts,
+                {0},
+                [&value](auto const& values) { value = *values[0]; },
+                [&failed](std::string const& /*unused*/, bool fatal) {
+                    failed = failed or fatal;
+                });
+        }
+        CHECK_FALSE(value);
+        CHECK_FALSE(failed);
+
+        auto const pending = map.GetPendingKeys();
+        CHECK_FALSE(pending.empty());
+
+        auto const cycle = map.DetectCycle();
+        REQUIRE(cycle);
+
+        // pending contains all keys from cycle (except last duplicate key)
+        CHECK_THAT(pending,
+                   Catch::Matchers::UnorderedEquals<int>(
+                       {cycle->begin(), cycle->end() - 1}));
+
+        // cycle contains keys in correct order
+        std::vector<int> expected{};
+        expected.reserve(kMaxVal + 1);
+        for (int i = cycle->at(0); i < cycle->at(0) + kMaxVal + 1; ++i) {
+            expected.emplace_back(i % kMaxVal);
+        }
+        CHECK_THAT(*cycle, Catch::Matchers::Equals(expected));
+    }
+
+    SECTION("No cycle and no unfinished keys") {
+        auto map = CountToMaxConsumer(kMaxVal);
+        {
+            TaskSystem ts;
+            map.ConsumeAfterKeysReady(
+                &ts,
+                {0},
+                [&value](auto const& values) { value = *values[0]; },
+                [&failed](std::string const& /*unused*/, bool fatal) {
+                    failed = failed or fatal;
+                });
+        }
+        REQUIRE(value);
+        CHECK(*value == kMaxVal);
+        CHECK_FALSE(failed);
+        CHECK_FALSE(map.DetectCycle());
+        CHECK(map.GetPendingKeys().empty());
+    }
+}
diff --git a/test/buildtool/multithreading/async_map_node.test.cpp b/test/buildtool/multithreading/async_map_node.test.cpp
new file mode 100644
index 00000000..9377e7f2
--- /dev/null
+++ b/test/buildtool/multithreading/async_map_node.test.cpp
@@ -0,0 +1,93 @@
+#include <mutex>
+#include <string>
+#include <thread>
+
+#include "catch2/catch.hpp"
+#include "src/buildtool/multithreading/async_map_node.hpp"
+#include "src/buildtool/multithreading/task_system.hpp"
+
+TEST_CASE("No task is queued if the node is never ready", "[async_map_node]") {
+    std::vector<int> tasks;
+    std::mutex m;
+    AsyncMapNode<int, bool> node_never_ready{0};
+    {
+        TaskSystem ts;
+        CHECK_FALSE(
+            node_never_ready.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+                std::unique_lock l{m};
+                // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+                tasks.push_back(0);
+            }));
+        CHECK_FALSE(
+            node_never_ready.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+                std::unique_lock l{m};
+                // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+                tasks.push_back(1);
+            }));
+        CHECK_FALSE(
+            node_never_ready.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+                std::unique_lock l{m};
+                // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+                tasks.push_back(2);
+            }));
+    }
+    CHECK(tasks.empty());
+}
+
+TEST_CASE("Value is set correctly", "[async_map_node]") {
+    AsyncMapNode<int, bool> node{0};
+    {
+        TaskSystem ts;
+        node.SetAndQueueAwaitingTasks(&ts, true);
+    }
+    CHECK(node.GetValue());
+}
+
+TEST_CASE("Tasks are queued correctly", "[async_map_node]") {
+    AsyncMapNode<int, std::string> node{0};
+    std::vector<int> tasks;
+    std::mutex m;
+    {
+        TaskSystem ts;
+        CHECK_FALSE(node.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+            std::unique_lock l{m};
+            // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+            tasks.push_back(0);
+        }));
+        CHECK_FALSE(node.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+            std::unique_lock l{m};
+            // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+            tasks.push_back(1);
+        }));
+        CHECK_FALSE(node.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+            std::unique_lock l{m};
+            // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+            tasks.push_back(2);
+        }));
+
+        {
+            std::unique_lock l{m};
+            CHECK(tasks.empty());
+        }
+        node.SetAndQueueAwaitingTasks(&ts, "ready");
+        CHECK(node.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+            std::unique_lock l{m};
+            // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+            tasks.push_back(3);
+        }));
+        CHECK(node.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+            std::unique_lock l{m};
+            // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+            tasks.push_back(4);
+        }));
+        CHECK(node.AddOrQueueAwaitingTask(&ts, [&tasks, &m]() {
+            std::unique_lock l{m};
+            // NOLINTNEXTLINE(readability-magic-numbers,cppcoreguidelines-avoid-magic-numbers)
+            tasks.push_back(5);
+        }));
+    }
+    CHECK(node.GetValue() == "ready");
+    CHECK_THAT(
+        tasks,
+        Catch::Matchers::UnorderedEquals(std::vector<int>{0, 1, 2, 3, 4, 5}));
+}
diff --git a/test/buildtool/multithreading/task.test.cpp b/test/buildtool/multithreading/task.test.cpp
new file mode 100644
index 00000000..40d641c3
--- /dev/null
+++ b/test/buildtool/multithreading/task.test.cpp
@@ -0,0 +1,328 @@
+#include "catch2/catch.hpp"
+#include "src/buildtool/multithreading/task.hpp"
+
+namespace {
+
+struct StatelessCallable {
+    void operator()() noexcept {}
+};
+
+struct ValueCaptureCallable {
+    explicit ValueCaptureCallable(int i) noexcept : number{i} {}
+
+    // NOLINTNEXTLINE
+    void operator()() noexcept { number += 5; }
+
+    int number;
+};
+
+struct RefCaptureCallable {
+    // NOLINTNEXTLINE(google-runtime-references)
+    explicit RefCaptureCallable(int& i) noexcept : number{i} {}
+
+    // NOLINTNEXTLINE
+    void operator()() noexcept { number += 3; }
+
+    int& number;
+};
+
+}  // namespace
+
+TEST_CASE("Default constructed task is empty", "[task]") {
+    Task t;
+    CHECK(!t);
+    CHECK(!(Task()));
+    CHECK(!(Task{}));
+}
+
+TEST_CASE("Task constructed from empty function is empty", "[task]") {
+    std::function<void()> empty_function;
+    Task t_from_empty_function{empty_function};
+
+    CHECK(!Task(std::function<void()>{}));
+    CHECK(!Task(empty_function));
+    CHECK(!t_from_empty_function);
+}
+
+TEST_CASE("Task constructed from user defined callable object is not empty",
+          "[task]") {
+    SECTION("Stateless struct") {
+        Task t{StatelessCallable{}};
+        StatelessCallable callable;
+        Task t_from_named_callable{callable};
+
+        CHECK(Task{StatelessCallable{}});
+        CHECK(Task{callable});
+        CHECK(t);
+        CHECK(t_from_named_callable);
+    }
+
+    SECTION("Statefull struct") {
+        SECTION("Reference capture") {
+            int a = 2;
+            Task t_ref{RefCaptureCallable{a}};
+            RefCaptureCallable three_adder{a};
+            Task t_from_named_callable_ref_capture{three_adder};
+
+            CHECK(Task{RefCaptureCallable{a}});
+            CHECK(Task{three_adder});
+            CHECK(t_ref);
+            CHECK(t_from_named_callable_ref_capture);
+        }
+
+        SECTION("Value capture") {
+            Task t_value{ValueCaptureCallable{1}};
+            ValueCaptureCallable callable{2};
+            Task t_from_named_callable_value_capture{callable};
+
+            CHECK(Task{ValueCaptureCallable{3}});
+            CHECK(Task{callable});
+            CHECK(t_value);
+            CHECK(t_from_named_callable_value_capture);
+        }
+    }
+}
+
+TEST_CASE("Task constructed from lambda is not empty", "[task]") {
+    SECTION("Stateless lambda") {
+        Task t{[]() {}};
+        auto callable = []() {};
+        Task t_from_named_callable{callable};
+
+        CHECK(Task{[]() {}});
+        CHECK(Task{callable});
+        CHECK(t);
+        CHECK(t_from_named_callable);
+    }
+
+    SECTION("Statefull lambda") {
+        SECTION("Reference capture") {
+            int a = 2;
+            Task t_ref{[&a]() { a += 3; }};
+            auto lambda = [&a]() { a += 3; };
+            Task t_from_named_lambda_ref_capture{lambda};
+
+            CHECK(Task{[&a]() { a += 3; }});
+            CHECK(Task{lambda});
+            CHECK(t_ref);
+            CHECK(t_from_named_lambda_ref_capture);
+        }
+
+        SECTION("Value capture") {
+            int a = 1;
+            // NOLINTNEXTLINE
+            Task t_value{[num = a]() mutable { num += 5; }};
+            // NOLINTNEXTLINE
+            auto lambda = [num = a]() mutable { num += 5; };
+            Task t_from_named_lambda_value_capture{lambda};
+
+            CHECK(Task{[num = a]() mutable { num += 5; }});
+            CHECK(Task{lambda});
+            CHECK(t_value);
+            CHECK(t_from_named_lambda_value_capture);
+        }
+    }
+}
+
+TEST_CASE("Task can be executed and doesn't steal contents", "[task]") {
+    SECTION("User defined object") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            ValueCaptureCallable add_five{num};
+            Task t_add_five{add_five};
+            CHECK(add_five.number == initial_value);
+            t_add_five();
+
+            // Internal data has been copied once again to the Task, so what is
+            // modified in the call to the task op() is not the data we can
+            // observe from the struct we created (add_five.number)
+            CHECK(add_five.number == initial_value);
+            CHECK(num == initial_value);
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            RefCaptureCallable add_three{num};
+            Task t_add_three{add_three};
+            CHECK(add_three.number == initial_value);
+            t_add_three();
+
+            // In this case, data modified by the task is the same than the one
+            // in the struct, so we can observe the change
+            CHECK(add_three.number == initial_value + 3);
+            CHECK(&num == &add_three.number);
+        }
+    }
+
+    SECTION("Anonymous lambda function") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            Task t_add_five{[a = num]() mutable { a += 5; }};
+            t_add_five();
+
+            // Internal data can not be observed, external data does not change
+            CHECK(num == initial_value);
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            Task t_add_three{[&num]() { num += 3; }};
+            t_add_three();
+
+            // Internal data can not be observed, external data changes
+            CHECK(num == initial_value + 3);
+        }
+    }
+
+    SECTION("Named lambda function") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            auto add_five = [a = num]() mutable { a += 5; };
+            Task t_add_five{add_five};
+            t_add_five();
+
+            // Internal data can not be observed, external data does not change
+            CHECK(num == initial_value);
+            // Lambda can be still called (we can't observe side effects)
+            add_five();
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            auto add_three = [&num]() { num += 3; };
+            Task t_add_three{add_three};
+            t_add_three();
+
+            // Internal data can not be observed, external data changes
+            CHECK(num == initial_value + 3);
+            // Lambda can be still called (and side effects are as expected)
+            add_three();
+            CHECK(num == initial_value + 6);
+        }
+    }
+
+    SECTION("std::function") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            std::function<void()> add_five{[a = num]() mutable { a += 5; }};
+            Task t_add_five{add_five};
+            t_add_five();
+
+            // Internal data can not be observed, external data does not change
+            CHECK(num == initial_value);
+            // Original function still valid (side effects not observable)
+            CHECK(add_five);
+            add_five();
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            std::function<void()> add_three{[&num]() { num += 3; }};
+            Task t_add_three{add_three};
+            t_add_three();
+
+            // Internal data can not be observed, external data changes
+            CHECK(num == initial_value + 3);
+            // Original function still valid (and side effects are as expected)
+            CHECK(add_three);
+            add_three();
+            CHECK(num == initial_value + 6);
+        }
+    }
+}
+
+TEST_CASE("Task moving from named object can be executed", "[task]") {
+    // Constructing Tasks from named objects using Task{std::move(named_object)}
+    // is only a way to explicitely express that the constructor from Task that
+    // will be called will treat `named_object` as an rvalue (temporary object).
+    // We could accomplish the same by using `Task t{Type{args}};` where `Type`
+    // is the type of the callable object.
+    SECTION("User defined object") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            ValueCaptureCallable add_five{num};
+            // NOLINTNEXTLINE
+            Task t_add_five{std::move(add_five)};
+            t_add_five();
+
+            // No observable side effects
+            CHECK(num == initial_value);
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            RefCaptureCallable add_three{num};
+            // NOLINTNEXTLINE
+            Task t_add_three{std::move(add_three)};
+            t_add_three();
+
+            // External data must have been affected by side effect but in this
+            // case `add_three` is a moved-from object so there is no guarrantee
+            // about the data it holds
+            CHECK(num == initial_value + 3);
+        }
+    }
+
+    // Note that for anonymous lambdas the move constructor of Task is the one
+    // that has already been tested
+    SECTION("Named lambda function") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            auto add_five = [a = num]() mutable { a += 5; };
+            Task t_add_five{std::move(add_five)};
+            t_add_five();
+
+            // Internal data can not be observed, external data does not change
+            CHECK(num == initial_value);
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            auto add_three = [&num]() { num += 3; };
+            Task t_add_three{std::move(add_three)};
+            t_add_three();
+
+            // Internal data can not be observed, external data changes
+            CHECK(num == initial_value + 3);
+        }
+    }
+
+    SECTION("std::function") {
+        SECTION("Value capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            std::function<void()> add_five{[a = num]() mutable { a += 5; }};
+            Task t_add_five{std::move(add_five)};
+            t_add_five();
+
+            // Internal data can not be observed, external data does not change
+            CHECK(num == initial_value);
+        }
+        SECTION("Reference capture") {
+            int const initial_value = 2;
+            int num = initial_value;
+            // NOLINTNEXTLINE
+            std::function<void()> add_three{[&num]() { num += 3; }};
+            Task t_add_three{std::move(add_three)};
+            t_add_three();
+
+            // Internal data can not be observed, external data changes
+            CHECK(num == initial_value + 3);
+        }
+    }
+}
diff --git a/test/buildtool/multithreading/task_system.test.cpp b/test/buildtool/multithreading/task_system.test.cpp
new file mode 100644
index 00000000..8488417c
--- /dev/null
+++ b/test/buildtool/multithreading/task_system.test.cpp
@@ -0,0 +1,225 @@
+#include <chrono>
+#include <mutex>
+#include <numeric>  // std::iota
+#include <string>
+#include <thread>
+#include <unordered_set>
+
+#include "catch2/catch.hpp"
+#include "src/buildtool/multithreading/task_system.hpp"
+#include "test/utils/container_matchers.hpp"
+
+namespace {
+
+enum class CallStatus { kNotExecuted, kExecuted };
+
+}  // namespace
+
+TEST_CASE("Basic", "[task_system]") {
+    SECTION("Empty task system terminates") {
+        { TaskSystem ts; }
+        CHECK(true);
+    }
+    SECTION("0-arguments constructor") {
+        TaskSystem ts;
+        CHECK(ts.NumberOfThreads() == std::thread::hardware_concurrency());
+    }
+    SECTION("1-argument constructor") {
+        std::size_t const desired_number_of_threads_in_ts =
+            GENERATE(1u, 2u, 5u, 10u, std::thread::hardware_concurrency());
+        TaskSystem ts(desired_number_of_threads_in_ts);
+        CHECK(ts.NumberOfThreads() == desired_number_of_threads_in_ts);
+    }
+}
+
+TEST_CASE("Side effects of tasks are reflected out of ts", "[task_system]") {
+    SECTION("Lambda function") {
+        auto status = CallStatus::kNotExecuted;
+        {  // Make sure that all tasks will be completed before the checks
+            TaskSystem ts;
+            ts.QueueTask([&status]() { status = CallStatus::kExecuted; });
+        }
+        CHECK(status == CallStatus::kExecuted);
+    }
+    SECTION("std::function") {
+        auto status = CallStatus::kNotExecuted;
+        {
+            TaskSystem ts;
+            std::function<void()> f{
+                [&status]() { status = CallStatus::kExecuted; }};
+            ts.QueueTask(f);
+        }
+        CHECK(status == CallStatus::kExecuted);
+    }
+    SECTION("Struct") {
+        auto s = CallStatus::kNotExecuted;
+        struct Callable {
+            explicit Callable(CallStatus* cs) : status{cs} {}
+            void operator()() const { *status = CallStatus::kExecuted; }
+            CallStatus* status;
+        };
+        Callable c{&s};
+        {
+            TaskSystem ts;
+            ts.QueueTask(c);
+        }
+        CHECK(&s == c.status);
+        CHECK(s == CallStatus::kExecuted);
+    }
+    SECTION("Lambda capturing `this` inside struct") {
+        std::string ext_name{};
+        struct Wrapper {
+            TaskSystem ts{};
+            std::string name{};
+
+            explicit Wrapper(std::string n) : name{std::move(n)} {}
+
+            void QueueSetAndCheck(std::string* ext) {
+                ts.QueueTask([this, ext]() {
+                    SetDefaultName();
+                    CheckDefaultName(ext);
+                });
+            }
+
+            void SetDefaultName() { name = "Default"; }
+
+            void CheckDefaultName(std::string* ext) const {
+                *ext = name;
+                CHECK(name == "Default");
+            }
+        };
+        {
+            Wrapper w{"Non-default name"};
+            w.QueueSetAndCheck(&ext_name);
+        }
+        CHECK(ext_name == "Default");
+    }
+}
+
+TEST_CASE("All tasks are executed", "[task_system]") {
+    std::size_t const number_of_tasks = 1000;
+    std::vector<int> tasks_executed;
+    std::vector<int> queued_tasks(number_of_tasks);
+    std::iota(std::begin(queued_tasks), std::end(queued_tasks), 0);
+    std::mutex m;
+
+    {
+        TaskSystem ts;
+        for (auto task_num : queued_tasks) {
+            ts.QueueTask([&tasks_executed, &m, task_num]() {
+                std::unique_lock l{m};
+                tasks_executed.push_back(task_num);
+            });
+        }
+    }
+
+    CHECK_THAT(tasks_executed,
+               HasSameElementsAs<std::vector<int>>(queued_tasks));
+}
+
+TEST_CASE("Task is executed even if it needs to wait for a long while",
+          "[task_system]") {
+    auto status = CallStatus::kNotExecuted;
+
+    // Calculate what would take for the task system to be constructed, queue a
+    // non-sleeping task, execute it and be destructed
+    auto const start_no_sleep = std::chrono::high_resolution_clock::now();
+    {
+        TaskSystem ts;
+        ts.QueueTask([&status]() { status = CallStatus::kExecuted; });
+    }
+    auto const end_no_sleep = std::chrono::high_resolution_clock::now();
+
+    status = CallStatus::kNotExecuted;
+
+    std::chrono::nanoseconds const sleep_time =
+        10 * std::chrono::duration_cast<std::chrono::nanoseconds>(
+                 end_no_sleep - start_no_sleep);
+    auto const start = std::chrono::high_resolution_clock::now();
+    {
+        TaskSystem ts;
+        ts.QueueTask([&status, sleep_time]() {
+            std::this_thread::sleep_for(sleep_time);
+            status = CallStatus::kExecuted;
+        });
+    }
+    auto const end = std::chrono::high_resolution_clock::now();
+    CHECK(end - start > sleep_time);
+    CHECK(status == CallStatus::kExecuted);
+}
+
+TEST_CASE("All threads run until work is done", "[task_system]") {
+    using namespace std::chrono_literals;
+    static auto const kNumThreads = std::thread::hardware_concurrency();
+    static auto const kFailTimeout = 10s;
+
+    std::mutex mutex{};
+    std::condition_variable cv{};
+    std::unordered_set<std::thread::id> tids{};
+
+    // Add thread id to set and wait for others to do the same.
+    auto store_id = [&tids, &mutex, &cv]() -> void {
+        std::unique_lock lock(mutex);
+        tids.emplace(std::this_thread::get_id());
+        cv.notify_all();
+        cv.wait_for(
+            lock, kFailTimeout, [&tids] { return tids.size() == kNumThreads; });
+    };
+
+    SECTION("single task produces multiple tasks") {
+        {
+            TaskSystem ts{kNumThreads};
+            // Wait some time for all threads to go to sleep.
+            std::this_thread::sleep_for(1s);
+
+            // Run singe task that creates the actual store tasks. All threads
+            // should stay alive until their corresponding queue is filled.
+            ts.QueueTask([&ts, &store_id] {
+                // One task per thread (assumes round-robin push to queues).
+                for (std::size_t i{}; i < ts.NumberOfThreads(); ++i) {
+                    ts.QueueTask([&store_id] { store_id(); });
+                }
+            });
+        }
+        CHECK(tids.size() == kNumThreads);
+    }
+
+    SECTION("multiple tasks reduce to one, which produces multiple tasks") {
+        atomic<std::size_t> counter{};
+
+        // All threads wait for counter, last thread creates 'store_id' tasks.
+        auto barrier = [&counter, &store_id](TaskSystem* ts) {
+            auto value = ++counter;
+            if (value == kNumThreads) {
+                counter.notify_all();
+
+                // Wait some time for other threads to go to sleep.
+                std::this_thread::sleep_for(1s);
+
+                // One task per thread (assumes round-robin push to queues).
+                for (std::size_t i{}; i < ts->NumberOfThreads(); ++i) {
+                    ts->QueueTask([&store_id] { store_id(); });
+                }
+            }
+            else {
+                while (value != kNumThreads) {
+                    counter.wait(value);
+                    value = counter;
+                }
+            }
+        };
+
+        {
+            TaskSystem ts{kNumThreads};
+
+            // Wait some time for all threads to go to sleep.
+            std::this_thread::sleep_for(1s);
+
+            // One task per thread (assumes round-robin push to queues).
+            for (std::size_t i{}; i < ts.NumberOfThreads(); ++i) {
+                ts.QueueTask([&barrier, &ts] { barrier(&ts); });
+            }
+        }
+        CHECK(tids.size() == kNumThreads);
+    }
+}