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.

1 files changed, 30 insertions, 0 deletions

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)},