expression language: add nub_left

Originally, the expression lanuage only contained a function to
deduplicate a list, keeping only the right-most occurence. The
reason was that this is the order needed for linking: a library
providing an open symbol has to come on the command line after the
library using that symbol (and hence making it an open symbol).
However, by now use cases have emerged that require a topological
sorting where definition comes before use; also, when composing
the value of PATH from fragments, we usually want to keep the first
occurrence in order for it to take precedence. Therefore, also
add "nub_left" as built-in function, allowing a more condense (and
slightly more efficient) description in rules instead of the
revserse-nub_right-reverse pattern.

4 files changed, 50 insertions, 2 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 56709f0f..22581d9e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -21,8 +21,8 @@ A feature release on top of `1.3.0`, backwards compatible.
   at the old location will not be used anymore while still using
   disk space.
 - The expression language has been extended to contain quote and
-  quasi-quote expressions, as well as a new built-in function
-  `"from_subdir"`.
+  quasi-quote expressions, as well as new built-in functions
+  `"from_subdir"`, `"nub_left"`.
 
 ### Fixes
 
diff --git a/doc/concepts/expressions.md b/doc/concepts/expressions.md
index c75f00dc..4db7c8cb 100644
--- a/doc/concepts/expressions.md
+++ b/doc/concepts/expressions.md
@@ -248,6 +248,11 @@ those) argument(s) to obtain the final result.
    result is the input list, except that for all duplicate
    values, all but the rightmost occurrence is removed.
 
+ - `"nub_list"` The argument has to be a list. It is an error
+   if that list contains (directly or indirectly) a name. The
+   result is the input list, except that for all duplicate
+   values, all but the leftmost occurrence is removed.
+
  - `"basename"` The argument has to be a string. This string is
    interpreted as a path, and the file name thereof is
    returned.
diff --git a/src/buildtool/build_engine/expression/evaluator.cpp b/src/buildtool/build_engine/expression/evaluator.cpp
index e2b3819d..350afa4e 100644
--- a/src/buildtool/build_engine/expression/evaluator.cpp
+++ b/src/buildtool/build_engine/expression/evaluator.cpp
@@ -279,6 +279,35 @@ auto NubRight(ExpressionPtr const& expr) -> ExpressionPtr {
     return ExpressionPtr{reverse_result};
 }
 
+auto NubLeft(ExpressionPtr const& expr) -> ExpressionPtr {
+    if (not expr->IsList()) {
+        throw Evaluator::EvaluationError{fmt::format(
+            "nub_left expects list but instead got: {}.", expr->ToString())};
+    }
+    if (not expr->IsCacheable()) {
+        throw Evaluator::EvaluationError{
+            fmt::format("Implicit comparison by passing name-containing value "
+                        "to nub_left: {}",
+                        expr->ToString())};
+    }
+    // short-cut evaluation for efficiency
+    if (expr->List().empty()) {
+        return expr;
+    }
+    auto const& list = expr->List();
+    auto result = Expression::list_t{};
+    result.reserve(list.size());
+    auto seen = std::unordered_set<ExpressionPtr>{};
+    seen.reserve(list.size());
+    std::for_each(list.begin(), list.end(), [&](auto const& l) {
+        if (not seen.contains(l)) {
+            result.push_back(l);
+            seen.insert(l);
+        }
+    });
+    return ExpressionPtr{result};
+}
+
 auto Range(ExpressionPtr const& expr) -> ExpressionPtr {
     std::size_t len = 0;
     if (expr->IsNumber() && expr->Number() > 0.0) {
@@ -1263,6 +1292,7 @@ auto const kBuiltInFunctions =
                           {"+", UnaryExpr(Addition)},
                           {"*", UnaryExpr(Multiplication)},
                           {"nub_right", UnaryExpr(NubRight)},
+                          {"nub_left", UnaryExpr(NubLeft)},
                           {"range", UnaryExpr(Range)},
                           {"change_ending", ChangeEndingExpr},
                           {"basename", UnaryExpr(BaseName)},
diff --git a/test/buildtool/build_engine/expression/expression.test.cpp b/test/buildtool/build_engine/expression/expression.test.cpp
index 938bd63f..83d6a2fe 100644
--- a/test/buildtool/build_engine/expression/expression.test.cpp
+++ b/test/buildtool/build_engine/expression/expression.test.cpp
@@ -946,6 +946,19 @@ TEST_CASE("Expression Evaluation", "[expression]") {  // NOLINT
              )"_json));
     }
 
+    SECTION("nub_left expression") {
+        auto expr = Expression::FromJson(R"(
+             {"type": "nub_left"
+             , "$1": ["a", "b", "b", "a", "c", "b", "a"]
+             })"_json);
+        REQUIRE(expr);
+
+        auto result = expr.Evaluate(env, fcts);
+        REQUIRE(result);
+        REQUIRE(result->IsList());
+        CHECK(result == Expression::FromJson(R"(["a", "b", "c"])"_json));
+    }
+
     SECTION("change_ending") {
         auto expr = Expression::FromJson(R"(
             { "type": "change_ending"