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>

1 files changed, 1401 insertions, 0 deletions

diff --git a/test/buildtool/build_engine/expression/expression.test.cpp b/test/buildtool/build_engine/expression/expression.test.cpp
new file mode 100644
index 00000000..180fcbe0
--- /dev/null
+++ b/test/buildtool/build_engine/expression/expression.test.cpp
@@ -0,0 +1,1401 @@
+#include "catch2/catch.hpp"
+#include "src/buildtool/build_engine/expression/configuration.hpp"
+#include "src/buildtool/build_engine/expression/expression.hpp"
+#include "src/buildtool/build_engine/expression/function_map.hpp"
+#include "test/utils/container_matchers.hpp"
+
+TEST_CASE("Expression access", "[expression]") {  // NOLINT
+    using namespace std::string_literals;
+    using path = std::filesystem::path;
+    using none_t = Expression::none_t;
+    using number_t = Expression::number_t;
+    using artifact_t = Expression::artifact_t;
+    using result_t = Expression::result_t;
+    using list_t = Expression::list_t;
+    using map_t = Expression::map_t;
+
+    auto none = ExpressionPtr{};
+    auto boolean = ExpressionPtr{true};
+    auto number = ExpressionPtr{number_t{1}};
+    auto string = ExpressionPtr{"2"s};
+    auto artifact = ExpressionPtr{artifact_t{path{"local_path"}}};
+    auto result = ExpressionPtr{result_t{boolean, number, string}};
+    auto list = ExpressionPtr{list_t{number}};
+    auto map = ExpressionPtr{map_t{{"3"s, number}}};
+
+    SECTION("Type checks") {
+        CHECK(none->IsNone());
+
+        CHECK(boolean->IsBool());
+        CHECK_FALSE(boolean->IsNone());
+
+        CHECK(number->IsNumber());
+        CHECK_FALSE(number->IsNone());
+
+        CHECK(string->IsString());
+        CHECK_FALSE(string->IsNone());
+
+        CHECK(artifact->IsArtifact());
+        CHECK_FALSE(artifact->IsNone());
+
+        CHECK(result->IsResult());
+        CHECK_FALSE(result->IsNone());
+
+        CHECK(list->IsList());
+        CHECK_FALSE(list->IsNone());
+
+        CHECK(map->IsMap());
+        CHECK_FALSE(map->IsNone());
+    }
+
+    SECTION("Throwing accessors") {
+        CHECK(boolean->Bool() == true);
+        CHECK_THROWS_AS(boolean->Number(), Expression::ExpressionTypeError);
+
+        CHECK(number->Number() == number_t{1});
+        CHECK_THROWS_AS(number->Bool(), Expression::ExpressionTypeError);
+
+        CHECK(string->String() == "2"s);
+        CHECK_THROWS_AS(string->Artifact(), Expression::ExpressionTypeError);
+
+        CHECK(artifact->Artifact() == artifact_t{path{"local_path"}});
+        CHECK_THROWS_AS(artifact->String(), Expression::ExpressionTypeError);
+
+        CHECK(result->Result() == result_t{boolean, number, string});
+        CHECK_THROWS_AS(result->String(), Expression::ExpressionTypeError);
+
+        CHECK_THAT(list->List(), Catch::Equals<ExpressionPtr>({number}));
+        CHECK_THROWS_AS(list->Map(), Expression::ExpressionTypeError);
+
+        REQUIRE(map->Map().at("3"s) == number);
+        CHECK_THROWS_AS(map->List(), Expression::ExpressionTypeError);
+    }
+
+    SECTION("Non-throwing accessors") {
+        CHECK(none->Value<none_t>());
+
+        CHECK(boolean->Value<bool>());
+        CHECK_FALSE(boolean->Value<none_t>());
+
+        CHECK(number->Value<number_t>());
+        CHECK_FALSE(number->Value<none_t>());
+
+        CHECK(string->Value<std::string>());
+        CHECK_FALSE(string->Value<none_t>());
+
+        CHECK(artifact->Value<artifact_t>());
+        CHECK_FALSE(artifact->Value<none_t>());
+
+        CHECK(result->Value<result_t>());
+        CHECK_FALSE(result->Value<none_t>());
+
+        CHECK(list->Value<list_t>());
+        CHECK_FALSE(list->Value<none_t>());
+
+        CHECK(map->Value<map_t>());
+        CHECK_FALSE(map->Value<none_t>());
+    }
+
+    SECTION("Non-throwing comparison operator") {
+        CHECK(none == none);
+        CHECK(none == Expression{});
+        CHECK(none == Expression::FromJson("null"_json));
+        CHECK(none != Expression{false});
+        CHECK(none != Expression{number_t{0}});
+        CHECK(none != Expression{""s});
+        CHECK(none != Expression{"0"s});
+        CHECK(none != Expression{list_t{}});
+        CHECK(none != Expression{map_t{}});
+
+        CHECK(boolean == boolean);
+        CHECK(boolean == true);
+        CHECK(boolean == Expression{true});
+        CHECK(boolean == Expression::FromJson("true"_json));
+        CHECK(boolean != false);
+        CHECK(boolean != Expression{false});
+        CHECK(boolean != number_t{1});
+        CHECK(boolean != number);
+        CHECK(boolean != Expression::FromJson("false"_json));
+
+        CHECK(number == number);
+        CHECK(number == number_t{1});
+        CHECK(number == Expression{number_t{1}});
+        CHECK(number == Expression::FromJson("1"_json));
+        CHECK(number != number_t{});
+        CHECK(number != Expression{number_t{}});
+        CHECK(number != true);
+        CHECK(number != boolean);
+        CHECK(number != Expression::FromJson("0"_json));
+
+        CHECK(string == string);
+        CHECK(string == "2"s);
+        CHECK(string == Expression{"2"s});
+        CHECK(string == Expression::FromJson(R"("2")"_json));
+        CHECK(string != ""s);
+        CHECK(string != Expression{""s});
+        CHECK(string != artifact_t{path{"local_path"}});
+        CHECK(string != artifact);
+        CHECK(string != Expression::FromJson(R"("")"_json));
+
+        CHECK(artifact == artifact);
+        CHECK(artifact == artifact_t{path{"local_path"}});
+        CHECK(artifact == Expression{artifact_t{path{"local_path"}}});
+        CHECK(artifact != ""s);
+        CHECK(artifact != string);
+
+        CHECK(result == result);
+        CHECK(result == result_t{boolean, number, string});
+        CHECK(result == Expression{result_t{boolean, number, string}});
+        CHECK(result != ""s);
+        CHECK(result != string);
+
+        CHECK(list == list);
+        CHECK(list == list_t{number});
+        CHECK(list == Expression{list_t{number}});
+        CHECK(list == Expression::FromJson("[1]"_json));
+        CHECK(list != list_t{});
+        CHECK(list != Expression{list_t{}});
+        CHECK(list != map);
+        CHECK(list != Expression{*map});
+        CHECK(list != Expression::FromJson(R"({"1":1})"_json));
+
+        CHECK(map == map);
+        CHECK(map == map_t{{"3"s, number}});
+        CHECK(map == Expression{map_t{{"3"s, number}}});
+        CHECK(map == Expression::FromJson(R"({"3":1})"_json));
+        CHECK(map != map_t{});
+        CHECK(map != Expression{map_t{}});
+        CHECK(map != list);
+        CHECK(map != Expression{*list});
+        CHECK(map != Expression::FromJson(R"(["3",1])"_json));
+
+        // compare nullptr != null != false != 0 != "" != [] != {}
+        auto exprs =
+            std::vector<ExpressionPtr>{ExpressionPtr{nullptr},
+                                       ExpressionPtr{artifact_t{path{""}}},
+                                       ExpressionPtr{result_t{}},
+                                       Expression::FromJson("null"_json),
+                                       Expression::FromJson("false"_json),
+                                       Expression::FromJson("0"_json),
+                                       Expression::FromJson(R"("")"_json),
+                                       Expression::FromJson("[]"_json),
+                                       Expression::FromJson("{}"_json)};
+        for (auto const& l : exprs) {
+            for (auto const& r : exprs) {
+                if (&l != &r) {
+                    CHECK(l != r);
+                }
+            }
+        }
+    }
+
+    SECTION("Throwing access operator") {
+        // operators with argument of type size_t expect list
+        CHECK_THROWS_AS(none[0], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(boolean[0], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(number[0], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(string[0], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(artifact[0], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(result[0], Expression::ExpressionTypeError);
+        CHECK(list[0] == number);
+        CHECK_THROWS_AS(map[0], Expression::ExpressionTypeError);
+
+        // operators with argument of type std::string expect map
+        CHECK_THROWS_AS(none["3"], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(boolean["3"], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(number["3"], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(string["3"], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(artifact["3"], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(result["3"], Expression::ExpressionTypeError);
+        CHECK_THROWS_AS(list["3"], Expression::ExpressionTypeError);
+        CHECK(map["3"] == number);
+    }
+}
+
+TEST_CASE("Expression from JSON", "[expression]") {
+    auto none = Expression::FromJson("null"_json);
+    REQUIRE(none);
+    CHECK(none->IsNone());
+
+    auto boolean = Expression::FromJson("true"_json);
+    REQUIRE(boolean);
+    REQUIRE(boolean->IsBool());
+    CHECK(boolean->Bool() == true);
+
+    auto number = Expression::FromJson("1"_json);
+    REQUIRE(number);
+    REQUIRE(number->IsNumber());
+    CHECK(number->Number() == 1);
+
+    auto string = Expression::FromJson(R"("foo")"_json);
+    REQUIRE(string);
+    REQUIRE(string->IsString());
+    CHECK(string->String() == "foo");
+
+    auto list = Expression::FromJson("[]"_json);
+    REQUIRE(list);
+    REQUIRE(list->IsList());
+    CHECK(list->List().empty());
+
+    auto map = Expression::FromJson("{}"_json);
+    REQUIRE(map);
+    REQUIRE(map->IsMap());
+    CHECK(map->Map().empty());
+}
+
+namespace {
+auto TestToJson(nlohmann::json const& json) -> void {
+    auto expr = Expression::FromJson(json);
+    REQUIRE(expr);
+    CHECK(expr->ToJson() == json);
+}
+}  // namespace
+
+TEST_CASE("Expression to JSON", "[expression]") {
+    TestToJson("null"_json);
+    TestToJson("true"_json);
+    TestToJson("1"_json);
+    TestToJson(R"("foo")"_json);
+    TestToJson("[]"_json);
+    TestToJson("{}"_json);
+}
+
+namespace {
+template <class T>
+concept ValidExpressionTypeOrPtr =
+    Expression::IsValidType<T>() or std::is_same_v<T, ExpressionPtr>;
+
+template <ValidExpressionTypeOrPtr T>
+auto Add(ExpressionPtr const& expr, std::string const& key, T const& by)
+    -> ExpressionPtr {
+    try {
+        auto new_map = Expression::map_t::underlying_map_t{};
+        new_map.emplace(key, by);
+        return ExpressionPtr{Expression::map_t{expr, new_map}};
+    } catch (...) {
+        return ExpressionPtr{nullptr};
+    }
+}
+
+template <ValidExpressionTypeOrPtr T>
+auto Replace(ExpressionPtr const& expr, std::string const& key, T const& by)
+    -> ExpressionPtr {
+    auto const& map = expr->Map();
+    if (not map.contains(key)) {
+        return ExpressionPtr{nullptr};
+    }
+    return Add(expr, key, by);
+}
+}  // namespace
+
+TEST_CASE("Expression Evaluation", "[expression]") {  // NOLINT
+    using namespace std::string_literals;
+    using number_t = Expression::number_t;
+    using list_t = Expression::list_t;
+
+    auto env = Configuration{};
+    auto fcts = FunctionMapPtr{};
+
+    auto foo = ExpressionPtr{"foo"s};
+    auto bar = ExpressionPtr{"bar"s};
+    auto baz = ExpressionPtr{"baz"s};
+
+    SECTION("list object") {
+        auto expr = Expression::FromJson(R"(["foo", "bar", "baz"])"_json);
+        REQUIRE(expr);
+        REQUIRE(expr->IsList());
+        CHECK(expr->List().size() == 3);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result->List().size() == 3);
+        CHECK(*result == *expr);
+    }
+
+    SECTION("map object without type") {
+        auto expr = Expression::FromJson(R"({"foo": "bar"})"_json);
+        REQUIRE(expr);
+        auto result = expr.Evaluate(env, fcts);
+        CHECK_FALSE(result);
+    }
+
+    fcts = FunctionMap::MakePtr(
+        "literal", [](auto&& /*eval*/, auto const& expr, auto const& /*env*/) {
+            return expr->Get("$1", Expression::none_t{});
+        });
+
+    SECTION("custom function") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "literal"
+            , "$1": "PLACEHOLDER" })"_json);
+        REQUIRE(expr);
+
+        auto literal = Expression::FromJson(R"({"foo": "bar"})"_json);
+        REQUIRE(literal);
+
+        expr = Replace(expr, "$1", literal);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        CHECK(result);
+        CHECK(*result == *literal);
+    }
+
+    SECTION("var expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "var"
+            , "name": "foo" })"_json);
+        REQUIRE(expr);
+
+        auto none_result = expr.Evaluate(env, fcts);
+        CHECK(none_result == Expression::FromJson(R"(null)"_json));
+
+        env = env.Update("foo", "bar"s);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsString());
+        CHECK(result == Expression::FromJson(R"("bar")"_json));
+
+        auto overwrite = expr.Evaluate(env.Update("foo", list_t{result}), fcts);
+        REQUIRE(overwrite);
+        REQUIRE(overwrite->IsList());
+        CHECK(overwrite == Expression::FromJson(R"(["bar"])"_json));
+    }
+
+    SECTION("if expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "if"
+            , "cond": "PLACEHOLDER"
+            , "then": "success"
+            , "else": "failure" })"_json);
+        REQUIRE(expr);
+
+        SECTION("Boolean condition") {
+            expr = Replace(expr, "cond", true);
+            REQUIRE(expr);
+            auto success = expr.Evaluate(env, fcts);
+            REQUIRE(success);
+            REQUIRE(success->IsString());
+            CHECK(success == Expression::FromJson(R"("success")"_json));
+
+            expr = Replace(expr, "cond", false);
+            REQUIRE(expr);
+            auto failure = expr.Evaluate(env, fcts);
+            REQUIRE(failure);
+            REQUIRE(failure->IsString());
+            CHECK(failure == Expression::FromJson(R"("failure")"_json));
+        }
+
+        SECTION("Number condition") {
+            expr = Replace(expr, "cond", number_t{1});
+            REQUIRE(expr);
+            auto success = expr.Evaluate(env, fcts);
+            REQUIRE(success);
+            REQUIRE(success->IsString());
+            CHECK(success == Expression::FromJson(R"("success")"_json));
+
+            expr = Replace(expr, "cond", number_t{0});
+            REQUIRE(expr);
+            auto failure = expr.Evaluate(env, fcts);
+            REQUIRE(failure);
+            REQUIRE(failure->IsString());
+            CHECK(failure == Expression::FromJson(R"("failure")"_json));
+        }
+
+        SECTION("String condition") {
+            expr = Replace(expr, "cond", "false"s);
+            REQUIRE(expr);
+            auto success = expr.Evaluate(env, fcts);
+            REQUIRE(success);
+            REQUIRE(success->IsString());
+            CHECK(success == Expression::FromJson(R"("success")"_json));
+
+            expr = Replace(expr, "cond", ""s);
+            REQUIRE(expr);
+            auto fail1 = expr.Evaluate(env, fcts);
+            REQUIRE(fail1);
+            REQUIRE(fail1->IsString());
+            CHECK(fail1 == Expression::FromJson(R"("failure")"_json));
+
+            expr = Replace(expr, "cond", "0"s);
+            REQUIRE(expr);
+            auto fail2 = expr.Evaluate(env, fcts);
+            REQUIRE(fail2);
+            REQUIRE(fail2->IsString());
+            CHECK(fail2 == Expression::FromJson(R"("failure")"_json));
+
+            expr = Replace(expr, "cond", "NO"s);
+            REQUIRE(expr);
+            auto fail3 = expr.Evaluate(env, fcts);
+            REQUIRE(fail3);
+            REQUIRE(fail3->IsString());
+            CHECK(fail3 == Expression::FromJson(R"("failure")"_json));
+        }
+
+        SECTION("List condition") {
+            expr = Replace(expr, "cond", list_t{ExpressionPtr{}});
+            REQUIRE(expr);
+            auto success = expr.Evaluate(env, fcts);
+            REQUIRE(success);
+            REQUIRE(success->IsString());
+            CHECK(success == Expression::FromJson(R"("success")"_json));
+
+            expr = Replace(expr, "cond", list_t{});
+            REQUIRE(expr);
+            auto failure = expr.Evaluate(env, fcts);
+            REQUIRE(failure);
+            REQUIRE(failure->IsString());
+            CHECK(failure == Expression::FromJson(R"("failure")"_json));
+        }
+
+        SECTION("Map condition") {
+            auto literal = Expression::FromJson(
+                R"({"type": "literal", "$1": {"foo": "bar"}})"_json);
+            REQUIRE(literal);
+            expr = Replace(expr, "cond", literal);
+            REQUIRE(expr);
+            auto success = expr.Evaluate(env, fcts);
+            REQUIRE(success);
+            REQUIRE(success->IsString());
+            CHECK(success == Expression::FromJson(R"("success")"_json));
+
+            auto empty =
+                Expression::FromJson(R"({"type": "literal", "$1": {}})"_json);
+            REQUIRE(empty);
+            expr = Replace(expr, "cond", empty);
+            REQUIRE(expr);
+            auto failure = expr.Evaluate(env, fcts);
+            REQUIRE(failure);
+            REQUIRE(failure->IsString());
+            CHECK(failure == Expression::FromJson(R"("failure")"_json));
+        }
+    }
+    SECTION("cond expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "cond"
+            , "cond":
+              [ [ { "type": "=="
+                  , "$1": {"type":"var", "name": "val", "default": ""}
+                  , "$2": 0
+                  }
+                , "number"
+                ]
+              , [ { "type": "=="
+                  , "$1": {"type":"var", "name": "val", "default": ""}
+                  , "$2": "0"
+                  }
+                , "string"
+                ]
+              , [ { "type": "=="
+                  , "$1": {"type":"var", "name": "val", "default": ""}
+                  , "$2": false
+                  }
+                , "boolean"
+                ]
+              , [ {"type":"var", "name": "val", "default": ""}, "first" ]
+              , [ {"type":"var", "name": "val", "default": ""}, "second" ]
+              ]})"_json);
+        REQUIRE(expr);
+
+        auto number = expr.Evaluate(env.Update("val", 0.0), fcts);
+        REQUIRE(number);
+        REQUIRE(number->IsString());
+        CHECK(number == Expression::FromJson(R"("number")"_json));
+
+        auto string = expr.Evaluate(env.Update("val", "0"s), fcts);
+        REQUIRE(string);
+        REQUIRE(string->IsString());
+        CHECK(string == Expression::FromJson(R"("string")"_json));
+
+        auto boolean = expr.Evaluate(env.Update("val", false), fcts);
+        REQUIRE(boolean);
+        REQUIRE(boolean->IsString());
+        CHECK(boolean == Expression::FromJson(R"("boolean")"_json));
+
+        auto first = expr.Evaluate(env.Update("val", true), fcts);
+        REQUIRE(first);
+        REQUIRE(first->IsString());
+        CHECK(first == Expression::FromJson(R"("first")"_json));
+
+        auto default1 = expr.Evaluate(env, fcts);
+        REQUIRE(default1);
+        REQUIRE(default1->IsList());
+        CHECK(default1 == Expression::FromJson(R"([])"_json));
+
+        expr = Add(expr, "default", "default"s);
+        auto default2 = expr.Evaluate(env, fcts);
+        REQUIRE(default2);
+        REQUIRE(default2->IsString());
+        CHECK(default2 == Expression::FromJson(R"("default")"_json));
+    }
+
+    SECTION("case expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "case"
+            , "expr": {"type": "var", "name": "val", "default": ""}
+            , "case":
+              { "foo": "FOO"
+              , "bar": {"type": "var", "name": "bar", "default": "BAR"}
+              }
+            })"_json);
+        REQUIRE(expr);
+
+        auto foo = expr.Evaluate(env.Update("val", "foo"s), fcts);
+        REQUIRE(foo);
+        REQUIRE(foo->IsString());
+        CHECK(foo == Expression::FromJson(R"("FOO")"_json));
+
+        auto bar = expr.Evaluate(env.Update("val", "bar"s), fcts);
+        REQUIRE(bar);
+        REQUIRE(bar->IsString());
+        CHECK(bar == Expression::FromJson(R"("BAR")"_json));
+
+        auto default1 = expr.Evaluate(env, fcts);
+        REQUIRE(default1);
+        REQUIRE(default1->IsList());
+        CHECK(default1 == Expression::FromJson(R"([])"_json));
+
+        expr = Add(expr, "default", "default"s);
+        auto default2 = expr.Evaluate(env, fcts);
+        REQUIRE(default2);
+        REQUIRE(default2->IsString());
+        CHECK(default2 == Expression::FromJson(R"("default")"_json));
+    }
+
+    SECTION("case* expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "case*"
+            , "expr": {"type": "var", "name": "val"}
+            , "case":
+              [ [false, "FOO"]
+              , [ {"type": "var", "name": "bar", "default": null}
+                , {"type": "var", "name": "bar", "default": "BAR"}
+                ]
+              , [0, {"type": "join", "$1": ["B", "A", "Z"]}]
+              ]
+            })"_json);
+        REQUIRE(expr);
+
+        auto foo = expr.Evaluate(env.Update("val", false), fcts);
+        REQUIRE(foo);
+        REQUIRE(foo->IsString());
+        CHECK(foo == Expression::FromJson(R"("FOO")"_json));
+
+        auto bar = expr.Evaluate(env, fcts);
+        REQUIRE(bar);
+        REQUIRE(bar->IsString());
+        CHECK(bar == Expression::FromJson(R"("BAR")"_json));
+
+        auto baz = expr.Evaluate(env.Update("val", 0.0), fcts);
+        REQUIRE(baz);
+        REQUIRE(baz->IsString());
+        CHECK(baz == Expression::FromJson(R"("BAZ")"_json));
+
+        auto default1 = expr.Evaluate(env.Update("val", ""s), fcts);
+        REQUIRE(default1);
+        REQUIRE(default1->IsList());
+        CHECK(default1 == Expression::FromJson(R"([])"_json));
+
+        expr = Add(expr, "default", "default"s);
+        auto default2 = expr.Evaluate(env.Update("val", ""s), fcts);
+        REQUIRE(default2);
+        REQUIRE(default2->IsString());
+        CHECK(default2 == Expression::FromJson(R"("default")"_json));
+    }
+
+    SECTION("== expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "=="
+            , "$1": "foo"
+            , "$2": "PLACEHOLDER"})"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "$2", "foo"s);
+        REQUIRE(expr);
+        auto success = expr.Evaluate(env, fcts);
+        REQUIRE(success);
+        REQUIRE(success->IsBool());
+        CHECK(success == Expression::FromJson("true"_json));
+
+        expr = Replace(expr, "$2", "bar"s);
+        REQUIRE(expr);
+        auto failure = expr.Evaluate(env, fcts);
+        REQUIRE(failure);
+        REQUIRE(failure->IsBool());
+        CHECK(failure == Expression::FromJson("false"_json));
+    }
+
+    SECTION("and expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "and"
+            , "$1": "PLACEHOLDER" })"_json);
+        REQUIRE(expr);
+
+        auto empty = ExpressionPtr{""s};
+
+        expr = Replace(expr, "$1", list_t{foo, bar});
+        REQUIRE(expr);
+        auto success = expr.Evaluate(env, fcts);
+        REQUIRE(success);
+        REQUIRE(success->IsBool());
+        CHECK(success == Expression::FromJson("true"_json));
+
+        expr = Replace(expr, "$1", list_t{foo, empty});
+        REQUIRE(expr);
+        auto failure = expr.Evaluate(env, fcts);
+        REQUIRE(failure);
+        REQUIRE(failure->IsBool());
+        CHECK(failure == Expression::FromJson("false"_json));
+
+        // test evaluation of list elements
+        expr = Replace(expr, "$1", list_t{foo, Expression::FromJson(R"(
+            {"type": "literal"
+            , "$1": true})"_json)});
+        REQUIRE(expr);
+        auto evaluated = expr.Evaluate(env, fcts);
+        REQUIRE(evaluated);
+        REQUIRE(evaluated->IsBool());
+        CHECK(evaluated == Expression::FromJson("true"_json));
+
+        // test short-circuit evaluation of logical and (static list)
+        auto static_list =
+            R"([true, false, {"type": "fail", "msg": "failed"}])"_json;
+        expr = Replace(expr, "$1", Expression::FromJson(static_list));
+        REQUIRE(expr);
+        auto static_result = expr.Evaluate(env, fcts);
+        REQUIRE(static_result);
+        REQUIRE(static_result->IsBool());
+        CHECK(static_result == Expression::FromJson("false"_json));
+
+        // test full evaluation of dynamic list (expression evaluating to list)
+        auto dynamic_list =
+            nlohmann::json{{"type", "context"}, {"$1", static_list}};
+        expr = Replace(expr, "$1", Expression::FromJson(dynamic_list));
+        REQUIRE(expr);
+        auto dyn_result = expr.Evaluate(env, fcts);
+        REQUIRE_FALSE(dyn_result);
+    }
+
+    SECTION("or expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "or"
+            , "$1": "PLACEHOLDER" })"_json);
+        REQUIRE(expr);
+
+        auto empty = ExpressionPtr{""s};
+
+        expr = Replace(expr, "$1", list_t{foo, bar});
+        REQUIRE(expr);
+        auto success = expr.Evaluate(env, fcts);
+        REQUIRE(success);
+        REQUIRE(success->IsBool());
+        CHECK(success == Expression::FromJson("true"_json));
+
+        expr = Replace(expr, "$1", list_t{foo, empty});
+        REQUIRE(expr);
+        auto failure = expr.Evaluate(env, fcts);
+        REQUIRE(failure);
+        REQUIRE(failure->IsBool());
+        CHECK(failure == Expression::FromJson("true"_json));
+
+        // test evaluation of list elements
+        expr = Replace(expr, "$1", list_t{foo, Expression::FromJson(R"(
+            {"type": "literal"
+            , "$1": true})"_json)});
+        REQUIRE(expr);
+        auto evaluated = expr.Evaluate(env, fcts);
+        REQUIRE(evaluated);
+        REQUIRE(evaluated->IsBool());
+        CHECK(evaluated == Expression::FromJson("true"_json));
+
+        // test short-circuit evaluation of logical or (static list)
+        auto static_list =
+            R"([false, true, {"type": "fail", "msg": "failed"}])"_json;
+        expr = Replace(expr, "$1", Expression::FromJson(static_list));
+        REQUIRE(expr);
+        auto static_result = expr.Evaluate(env, fcts);
+        REQUIRE(static_result);
+        REQUIRE(static_result->IsBool());
+        CHECK(static_result == Expression::FromJson("true"_json));
+
+        // test full evaluation of dynamic list (expression evaluating to list)
+        auto dynamic_list =
+            nlohmann::json{{"type", "context"}, {"$1", static_list}};
+        expr = Replace(expr, "$1", Expression::FromJson(dynamic_list));
+        REQUIRE(expr);
+        auto dyn_result = expr.Evaluate(env, fcts);
+        REQUIRE_FALSE(dyn_result);
+    }
+
+    SECTION("+ expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "+"
+            , "$1": ["foo"]
+            , "$2": "PLACEHOLDER" })"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "$2", list_t{bar});
+        REQUIRE(expr);
+        auto success = expr.Evaluate(env, fcts);
+        REQUIRE(success);
+        REQUIRE(success->IsList());
+        CHECK(success == Expression::FromJson(R"(["foo", "bar"])"_json));
+
+        expr = Replace(expr, "$2", bar);
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+    }
+
+    SECTION("++ expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "++"
+            , "$1": [ ["foo"]
+                    , ["bar", "baz"]]})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(["foo", "bar", "baz"])"_json));
+    }
+
+    SECTION("nub_right expression") {
+        auto expr = Expression::FromJson(R"(
+             {"type": "nub_right"
+             , "$1": ["-lfoo", "-lbar", "-lbaz", "-lbar"]
+             })"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result ==
+              Expression::FromJson(R"(["-lfoo", "-lbaz", "-lbar"])"_json));
+    }
+
+    SECTION("nub_right expression 2") {
+        auto expr = Expression::FromJson(R"(
+             {"type": "nub_right"
+             , "$1":
+               { "type": "++"
+               , "$1":
+                 [ ["libg.a"]
+                 , ["libe.a", "libd.a", "libc.a", "liba.a", "libb.a"]
+                 , ["libf.a", "libc.a", "libd.a", "libb.a", "liba.a"]
+                 , ["libc.a", "liba.a", "libb.a"]
+                 , ["libd.a", "libb.a", "liba.a"]
+                 ]
+               }
+             })"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(
+             ["libg.a", "libe.a", "libf.a", "libc.a", "libd.a", "libb.a", "liba.a"]
+             )"_json));
+    }
+
+    SECTION("change_ending") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "change_ending"
+            , "$1": "PLACEHOLDER"
+            , "ending": "_suffix" })"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "$1", ""s);
+        REQUIRE(expr);
+        auto empty_path = expr.Evaluate(env, fcts);
+        REQUIRE(empty_path);
+        REQUIRE(empty_path->IsString());
+        CHECK(empty_path == Expression::FromJson(R"("_suffix")"_json));
+
+        expr = Replace(expr, "$1", ".rc"s);
+        REQUIRE(expr);
+        auto hidden_file = expr.Evaluate(env, fcts);
+        REQUIRE(hidden_file);
+        REQUIRE(hidden_file->IsString());
+        CHECK(hidden_file == Expression::FromJson(R"(".rc_suffix")"_json));
+
+        expr = Replace(expr, "$1", "/root/path/file.txt"s);
+        REQUIRE(expr);
+        auto full_path = expr.Evaluate(env, fcts);
+        REQUIRE(full_path);
+        REQUIRE(full_path->IsString());
+        CHECK(full_path ==
+              Expression::FromJson(R"("/root/path/file_suffix")"_json));
+    }
+
+    SECTION("basename") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "basename"
+            , "$1": "PLACEHOLDER"
+            })"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "$1", "foo.c"s);
+        REQUIRE(expr);
+        auto plain_file = expr.Evaluate(env, fcts);
+        REQUIRE(plain_file);
+        REQUIRE(plain_file->IsString());
+        CHECK(plain_file == Expression::FromJson(R"("foo.c")"_json));
+
+        expr = Replace(expr, "$1", "/path/to/file.txt"s);
+        REQUIRE(expr);
+        auto stripped_path = expr.Evaluate(env, fcts);
+        REQUIRE(stripped_path);
+        REQUIRE(stripped_path->IsString());
+        CHECK(stripped_path == Expression::FromJson(R"("file.txt")"_json));
+    }
+
+    SECTION("join") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "join"
+            , "$1": "PLACEHOLDER"
+            , "separator": ";" })"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "$1", list_t{});
+        REQUIRE(expr);
+        auto empty = expr.Evaluate(env, fcts);
+        REQUIRE(empty);
+        REQUIRE(empty->IsString());
+        CHECK(empty == Expression::FromJson(R"("")"_json));
+
+        expr = Replace(expr, "$1", list_t{foo});
+        REQUIRE(expr);
+        auto single = expr.Evaluate(env, fcts);
+        REQUIRE(single);
+        REQUIRE(single->IsString());
+        CHECK(single == Expression::FromJson(R"("foo")"_json));
+
+        expr = Replace(expr, "$1", list_t{foo, bar, baz});
+        REQUIRE(expr);
+        auto multi = expr.Evaluate(env, fcts);
+        REQUIRE(multi);
+        REQUIRE(multi->IsString());
+        CHECK(multi == Expression::FromJson(R"("foo;bar;baz")"_json));
+
+        expr = Replace(expr, "$1", foo);
+        REQUIRE(expr);
+        auto string = expr.Evaluate(env, fcts);
+        REQUIRE(string);
+        REQUIRE(string->IsString());
+        CHECK(string == Expression::FromJson(R"("foo")"_json));
+
+        // only list of strings or string is allowed
+        expr = Replace(expr, "$1", list_t{foo, ExpressionPtr{number_t{}}});
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+
+        expr = Replace(expr, "$1", number_t{});
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+    }
+
+    SECTION("join_cmd expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "join_cmd"
+            , "$1": ["foo", "bar's", "baz"]})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsString());
+        CHECK(result ==
+              Expression::FromJson(R"("'foo' 'bar'\\''s' 'baz'")"_json));
+    }
+
+    SECTION("escape_chars expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "escape_chars"
+            , "$1": "escape me X"
+            , "chars": "abcX"
+            , "escape_prefix": "X"})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsString());
+        CHECK(result == Expression::FromJson(R"("esXcXape me XX")"_json));
+    }
+
+    SECTION("keys expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "keys"
+            , "$1": { "type": "literal"
+                    , "$1": { "foo": true
+                            , "bar": false
+                            , "baz": true }}})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(["bar", "baz", "foo"])"_json));
+    }
+
+    SECTION("values expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "values"
+            , "$1": { "type": "literal"
+                    , "$1": { "foo": true
+                            , "bar": "foo"
+                            , "baz": 1 }}})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(["foo", 1, true])"_json));
+    }
+
+    SECTION("lookup expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "lookup"
+            , "key": "PLACEHOLDER"
+            , "map": { "type": "literal"
+                    , "$1": { "foo": true
+                            , "bar": 1 }}})"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "key", "foo"s);
+        REQUIRE(expr);
+        auto result_foo = expr.Evaluate(env, fcts);
+        REQUIRE(result_foo);
+        CHECK(result_foo == Expression::FromJson("true"_json));
+
+        expr = Replace(expr, "key", "bar"s);
+        REQUIRE(expr);
+        auto result_bar = expr.Evaluate(env, fcts);
+        REQUIRE(result_bar);
+        CHECK(result_bar == Expression::FromJson("1"_json));
+
+        // key baz is missing
+        expr = Replace(expr, "key", "baz"s);
+        REQUIRE(expr);
+        auto result_baz = expr.Evaluate(env, fcts);
+        REQUIRE(result_baz);
+        CHECK(result_baz == Expression::FromJson("null"_json));
+
+        // map is not mapping
+        expr = Replace(expr, "map", list_t{});
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+
+        // key is not string
+        expr = Replace(expr, "key", number_t{});
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+    }
+
+    SECTION("lookup with default") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "lookup"
+            , "key": "PLACEHOLDER"
+            , "map": { "type": "literal"
+                     , "$1": { "foo": false
+                             , "bar": 1
+                             , "baz" : null}}
+            , "default" : { "type" : "join"
+                          , "separator": "x"
+                          , "$1": ["a", "b"]}})"_json);
+        REQUIRE(expr);
+
+        // Key present (and false)
+        expr = Replace(expr, "key", "foo"s);
+        REQUIRE(expr);
+        auto result_foo = expr.Evaluate(env, fcts);
+        REQUIRE(result_foo);
+        CHECK(result_foo == Expression::FromJson("false"_json));
+
+        // Key present but value is null
+        expr = Replace(expr, "key", "baz"s);
+        REQUIRE(expr);
+        auto result_baz = expr.Evaluate(env, fcts);
+        REQUIRE(result_baz);
+        CHECK(result_baz == Expression::FromJson(R"("axb")"_json));
+
+        // Key not present
+        expr = Replace(expr, "key", "missing"s);
+        REQUIRE(expr);
+        auto result_missing = expr.Evaluate(env, fcts);
+        REQUIRE(result_missing);
+        CHECK(result_missing == Expression::FromJson(R"("axb")"_json));
+    }
+
+    SECTION("empty_map expression") {
+        auto expr = Expression::FromJson(R"({"type": "empty_map"})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result == Expression::FromJson("{}"_json));
+    }
+
+    SECTION("singleton_map expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "singleton_map"
+            , "key": "foo"
+            , "value": "bar"})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result == Expression::FromJson(R"({"foo": "bar"})"_json));
+    }
+
+    SECTION("disjoint_map_union expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "disjoint_map_union"
+            , "$1": "PLACEHOLDER" })"_json);
+        REQUIRE(expr);
+
+        auto literal_foo = Expression::FromJson(
+            R"({"type": "literal", "$1": {"foo":true}})"_json);
+        REQUIRE(literal_foo);
+        auto literal_foo_false = Expression::FromJson(
+            R"({"type": "literal", "$1": {"foo":false}})"_json);
+        REQUIRE(literal_foo_false);
+        auto literal_bar = Expression::FromJson(
+            R"({"type": "literal", "$1": {"bar":false}})"_json);
+        REQUIRE(literal_bar);
+
+        expr = Replace(expr, "$1", list_t{literal_foo, literal_bar});
+        REQUIRE(expr);
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result ==
+              Expression::FromJson(R"({"foo": true, "bar": false})"_json));
+
+        // duplicate foo, but with same value
+        expr = Replace(expr, "$1", list_t{literal_foo, literal_foo});
+        REQUIRE(expr);
+        result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result == Expression::FromJson(R"({"foo": true})"_json));
+
+        // duplicate foo, but with different value
+        expr = Replace(expr, "$1", list_t{literal_foo, literal_foo_false});
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+
+        // empty list should produce empty map
+        expr = Replace(expr, "$1", list_t{});
+        REQUIRE(expr);
+        auto empty = expr.Evaluate(env, fcts);
+        REQUIRE(empty);
+        REQUIRE(empty->IsMap());
+        REQUIRE(empty == Expression::FromJson("{}"_json));
+    }
+
+    SECTION("map_union expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "map_union"
+            , "$1": { "type": "literal"
+                    , "$1": [ {"foo": true}
+                            , {"bar": false}] }})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result ==
+              Expression::FromJson(R"({"foo": true, "bar": false})"_json));
+
+        // empty list should produce empty map
+        expr = Expression::FromJson(R"({"type": "map_union", "$1": []})"_json);
+        REQUIRE(expr);
+        auto empty = expr.Evaluate(env, fcts);
+        REQUIRE(empty);
+        REQUIRE(empty->IsMap());
+        REQUIRE(empty == Expression::FromJson("{}"_json));
+    }
+
+    SECTION("to_subdir expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "to_subdir"
+            , "subdir": "prefix"
+            , "$1": { "type": "literal"
+                    , "$1": { "foo": "hello"
+                            , "bar": "world" }}})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result ==
+              Expression::FromJson(
+                  R"({"prefix/foo": "hello", "prefix/bar": "world"})"_json));
+    }
+
+    SECTION("flat to_subdir without proper conflict") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "to_subdir"
+            , "subdir": "prefix"
+            , "flat" : "YES"
+            , "$1": { "type": "literal"
+                    , "$1": { "foobar/data/foo": "hello"
+                            , "foobar/include/foo": "hello"
+                            , "bar": "world" }}})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsMap());
+        CHECK(result ==
+              Expression::FromJson(
+                  R"({"prefix/foo": "hello", "prefix/bar": "world"})"_json));
+    }
+
+    SECTION("flat to_subdir with conflict") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "to_subdir"
+            , "subdir": "prefix"
+            , "flat" : "YES"
+            , "$1": { "type": "literal"
+                    , "$1": { "foobar/data/foo": "HELLO"
+                            , "foobar/include/foo": "hello"
+                            , "bar": "world" }}})"_json);
+        REQUIRE(expr);
+
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+    }
+
+    fcts = FunctionMap::MakePtr(
+        fcts, "concat", [](auto&& eval, auto const& expr, auto const& env) {
+            auto p1 = eval(expr->Get("$1", ""s), env);
+            auto p2 = eval(expr->Get("$2", ""s), env);
+            return ExpressionPtr{p1->String() + p2->String()};
+        });
+
+    SECTION("foreach expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "foreach"
+            , "var": "x"
+            , "range": ["foo", "bar", "baz"]
+            , "body": { "type": "concat"
+                      , "$1": { "type": "var"
+                              , "name": "x" }
+                      , "$2": "y" }})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result ==
+              Expression::FromJson(R"(["fooy", "bary", "bazy"])"_json));
+    }
+
+    SECTION("foreach_map expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "foreach_map"
+            , "var_key": "key"
+            , "var_val": "val"
+            , "body": { "type": "concat"
+                      , "$1": { "type": "var"
+                              , "name": "key" }
+                      , "$2": { "type": "var"
+                              , "name": "val" }}})"_json);
+        REQUIRE(expr);
+
+        // range is missing (should default to empty map)
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"([])"_json));
+
+        // range is map with one entry
+        expr = Add(expr, "range", Expression::FromJson(R"(
+            { "type": "literal"
+            , "$1": {"foo": "bar"}})"_json));
+        REQUIRE(expr);
+
+        result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(["foobar"])"_json));
+
+        // range is map with multiple entries
+        expr = Replace(expr, "range", Expression::FromJson(R"(
+            { "type": "literal"
+            , "$1": {"foo": "bar", "bar": "baz"}})"_json));
+        REQUIRE(expr);
+
+        result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(["barbaz", "foobar"])"_json));
+
+        // fail if range is string
+        expr = Replace(expr, "range", Expression::FromJson(R"("foo")"_json));
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+
+        // fail if range is number
+        expr = Replace(expr, "range", Expression::FromJson(R"("4711")"_json));
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+
+        // fail if range is Boolean
+        expr = Replace(expr, "range", Expression::FromJson(R"("true")"_json));
+        REQUIRE(expr);
+        CHECK_FALSE(expr.Evaluate(env, fcts));
+    }
+
+    SECTION("foldl expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "foldl"
+            , "var": "x"
+            , "range": ["bar", "baz"]
+            , "accum_var": "a"
+            , "start": "foo"
+            , "body": { "type": "concat"
+                      , "$1": { "type": "var"
+                              , "name": "x" }
+                      , "$2": { "type": "var"
+                              , "name": "a" }}})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsString());
+        CHECK(result == Expression::FromJson(R"("bazbarfoo")"_json));
+    }
+
+    SECTION("let* expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "let*"
+            , "bindings": [ ["foo", "foo"]
+                          , ["bar", "bar"] ]
+            , "body": { "type": "concat"
+                      , "$1": { "type": "var"
+                              , "name": "foo" }
+                      , "$2": { "type": "var"
+                              , "name": "bar" }}})"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsString());
+        CHECK(result == Expression::FromJson(R"("foobar")"_json));
+    }
+
+    SECTION("sequentiallity of let* expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "let*"
+            , "bindings":
+              [ ["one", "foo"]
+              , ["two", { "type": "join"
+                        , "$1": [ {"type": "var", "name" : "one"}
+                                , {"type": "var", "name" : "one"} ]}]
+              , ["four", { "type": "join"
+                         , "$1": [ {"type": "var", "name" : "two"}
+                                 , {"type": "var", "name" : "two"} ]}]
+              ]
+            , "body": { "type" : "var"
+                      , "name" : "four" }
+            })"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsString());
+        CHECK(result == Expression::FromJson(R"("foofoofoofoo")"_json));
+    }
+
+    SECTION("concat_target_name expression") {
+        auto expr = Expression::FromJson(R"(
+            { "type": "concat_target_name"
+            , "$1": "PLACEHOLDER"
+            , "$2": "_suffix" })"_json);
+        REQUIRE(expr);
+
+        expr = Replace(expr, "$1", "foo"s);
+        REQUIRE(expr);
+        auto str_result = expr.Evaluate(env, fcts);
+        REQUIRE(str_result);
+        REQUIRE(str_result->IsString());
+        CHECK(str_result == Expression::FromJson(R"("foo_suffix")"_json));
+
+        auto dep_tgt = Expression::FromJson(R"(["subdir", "bar"])"_json);
+        REQUIRE(dep_tgt);
+        expr = Replace(expr, "$1", dep_tgt);
+        REQUIRE(expr);
+        auto dep_result = expr.Evaluate(env, fcts);
+        REQUIRE(dep_result);
+        REQUIRE(dep_result->IsList());
+        CHECK(dep_result ==
+              Expression::FromJson(R"(["subdir", "bar_suffix"])"_json));
+    }
+}
+
+TEST_CASE("Expression hash computation", "[expression]") {
+    using namespace std::string_literals;
+    using path = std::filesystem::path;
+    using number_t = Expression::number_t;
+    using artifact_t = Expression::artifact_t;
+    using result_t = Expression::result_t;
+    using list_t = Expression::list_t;
+    using map_t = Expression::map_t;
+
+    auto none = ExpressionPtr{};
+    auto boolean = ExpressionPtr{false};
+    auto number = ExpressionPtr{number_t{}};
+    auto string = ExpressionPtr{""s};
+    auto artifact = ExpressionPtr{artifact_t{path{""}}};
+    auto result = ExpressionPtr{result_t{}};
+    auto list = ExpressionPtr{list_t{}};
+    auto map = ExpressionPtr{map_t{}};
+
+    CHECK_FALSE(none->ToHash().empty());
+    CHECK(none->ToHash() == Expression{}.ToHash());
+
+    CHECK_FALSE(boolean->ToHash().empty());
+    CHECK(boolean->ToHash() == Expression{false}.ToHash());
+    CHECK_FALSE(boolean->ToHash() == Expression{true}.ToHash());
+
+    CHECK_FALSE(number->ToHash().empty());
+    CHECK(number->ToHash() == Expression{number_t{}}.ToHash());
+    CHECK_FALSE(number->ToHash() == Expression{number_t{1}}.ToHash());
+
+    CHECK_FALSE(string->ToHash().empty());
+    CHECK(string->ToHash() == Expression{""s}.ToHash());
+    CHECK_FALSE(string->ToHash() == Expression{" "s}.ToHash());
+
+    CHECK_FALSE(artifact->ToHash().empty());
+    CHECK(artifact->ToHash() == Expression{artifact_t{path{""}}}.ToHash());
+    CHECK_FALSE(artifact->ToHash() ==
+                Expression{artifact_t{path{" "}}}.ToHash());
+
+    CHECK_FALSE(result->ToHash().empty());
+    CHECK(result->ToHash() == Expression{result_t{}}.ToHash());
+    CHECK_FALSE(result->ToHash() == Expression{result_t{boolean}}.ToHash());
+
+    CHECK_FALSE(list->ToHash().empty());
+    CHECK(list->ToHash() == Expression{list_t{}}.ToHash());
+    CHECK_FALSE(list->ToHash() == Expression{list_t{number}}.ToHash());
+    CHECK_FALSE(list->ToHash() == Expression{map_t{{""s, number}}}.ToHash());
+
+    CHECK_FALSE(map->ToHash().empty());
+    CHECK(map->ToHash() == Expression{map_t{}}.ToHash());
+    CHECK_FALSE(map->ToHash() == Expression{map_t{{""s, number}}}.ToHash());
+    CHECK_FALSE(map->ToHash() == Expression{list_t{string, number}}.ToHash());
+
+    auto exprs = std::vector<ExpressionPtr>{
+        none, boolean, number, string, artifact, result, list, map};
+    for (auto const& l : exprs) {
+        for (auto const& r : exprs) {
+            if (&l != &r) {
+                CHECK_FALSE(l->ToHash() == r->ToHash());
+            }
+        }
+    }
+}