primops: lazy evaluation of replaceStrings replacements

The primop `builtins.replaceStrings` currently always strictly evaluates the
replacement strings, however time and space are wasted for their computation
if the corresponding pattern do not occur in the input string. This commit
makes the evaluation of the replacement strings lazy by deferring their
evaluation to when the corresponding pattern are matched and memoize the result
for efficient retrieval on subsequent matches.

The testcases for replaceStrings was updated to check for lazy evaluation
of the replacements. A note was also added in the release notes to
document the behavior change.

5 files changed, 17 insertions, 14 deletions

diff --git a/doc/manual/src/release-notes/rl-next.md b/doc/manual/src/release-notes/rl-next.md
index bc0d41bdf..f92625887 100644
--- a/doc/manual/src/release-notes/rl-next.md
+++ b/doc/manual/src/release-notes/rl-next.md
@@ -4,3 +4,4 @@
   The number of parallel downloads (also known as substitutions) has been separated from the [`--max-jobs` setting](../command-ref/conf-file.md#conf-max-jobs).
   The new setting is called [`max-substitution-jobs`](../command-ref/conf-file.md#conf-max-substitution-jobs).
   The number of parallel downloads is now set to 16 by default (previously, the default was 1 due to the coupling to build jobs).
+- The function `builtins.replaceStrings` is now lazy in the value of its second argument `to`, that is a replacee in `to` is only evaluated when its corresponding pattern in `from` is matched in the string `s`.
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index cfae1e5f8..0f3b0a9fe 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -3910,13 +3910,8 @@ static void prim_replaceStrings(EvalState & state, const PosIdx pos, Value * * a
     for (auto elem : args[0]->listItems())
         from.emplace_back(state.forceString(*elem, pos, "while evaluating one of the strings to replace passed to builtins.replaceStrings"));
 
-    std::vector<std::pair<std::string, NixStringContext>> to;
-    to.reserve(args[1]->listSize());
-    for (auto elem : args[1]->listItems()) {
-        NixStringContext ctx;
-        auto s = state.forceString(*elem, ctx, pos, "while evaluating one of the replacement strings passed to builtins.replaceStrings");
-        to.emplace_back(s, std::move(ctx));
-    }
+    std::unordered_map<size_t, std::string> cache;
+    auto to = args[1]->listItems();
 
     NixStringContext context;
     auto s = state.forceString(*args[2], context, pos, "while evaluating the third argument passed to builtins.replaceStrings");
@@ -3927,10 +3922,19 @@ static void prim_replaceStrings(EvalState & state, const PosIdx pos, Value * * a
         bool found = false;
         auto i = from.begin();
         auto j = to.begin();
-        for (; i != from.end(); ++i, ++j)
+        size_t j_index = 0;
+        for (; i != from.end(); ++i, ++j, ++j_index)
             if (s.compare(p, i->size(), *i) == 0) {
                 found = true;
-                res += j->first;
+                auto v = cache.find(j_index);
+                if (v == cache.end()) {
+                    NixStringContext ctx;
+                    auto ts = state.forceString(**j, ctx, pos, "while evaluating one of the replacement strings passed to builtins.replaceStrings");
+                    v = (cache.emplace(j_index, ts)).first;
+                    for (auto& path : ctx)
+                        context.insert(path);
+                }
+                res += v->second;
                 if (i->empty()) {
                     if (p < s.size())
                         res += s[p];
@@ -3938,9 +3942,6 @@ static void prim_replaceStrings(EvalState & state, const PosIdx pos, Value * * a
                 } else {
                     p += i->size();
                 }
-                for (auto& path : j->second)
-                    context.insert(path);
-                j->second.clear();
                 break;
             }
         if (!found) {
diff --git a/src/libexpr/tests/error_traces.cc b/src/libexpr/tests/error_traces.cc
index 24e95ac39..285651256 100644
--- a/src/libexpr/tests/error_traces.cc
+++ b/src/libexpr/tests/error_traces.cc
@@ -171,7 +171,7 @@ namespace nix {
                       hintfmt("value is %s while a string was expected", "an integer"),
                       hintfmt("while evaluating one of the strings to replace passed to builtins.replaceStrings"));
 
-        ASSERT_TRACE2("replaceStrings [ \"old\" ] [ true ] {}",
+        ASSERT_TRACE2("replaceStrings [ \"oo\" ] [ true ] \"foo\"",
                       TypeError,
                       hintfmt("value is %s while a string was expected", "a Boolean"),
                       hintfmt("while evaluating one of the replacement strings passed to builtins.replaceStrings"));
diff --git a/tests/lang/eval-okay-replacestrings.exp b/tests/lang/eval-okay-replacestrings.exp
index 72e8274d8..eac67c5fe 100644
--- a/tests/lang/eval-okay-replacestrings.exp
+++ b/tests/lang/eval-okay-replacestrings.exp
@@ -1 +1 @@
-[ "faabar" "fbar" "fubar" "faboor" "fubar" "XaXbXcX" "X" "a_b" ]
+[ "faabar" "fbar" "fubar" "faboor" "fubar" "XaXbXcX" "X" "a_b" "fubar" ]
diff --git a/tests/lang/eval-okay-replacestrings.nix b/tests/lang/eval-okay-replacestrings.nix
index bd8031fc0..a803e6519 100644
--- a/tests/lang/eval-okay-replacestrings.nix
+++ b/tests/lang/eval-okay-replacestrings.nix
@@ -8,4 +8,5 @@ with builtins;
   (replaceStrings [""] ["X"] "abc")
   (replaceStrings [""] ["X"] "")
   (replaceStrings ["-"] ["_"] "a-b")
+  (replaceStrings ["oo" "XX"] ["u" (throw "unreachable")] "foobar")
 ]