libutil: make rewriteStrings sound

this is used in CA rewriting, replacement of placeholders in
derivations, generating scripts for devShells, and some more
places. in all of these transitive replacements are unsound,
and overlapping replacements would be as well. there even is
a test that transitive replacements do not happen (in the CA
RewriteSink suite), but none for overlapping replacements. a
minimally surprising binary rewriter surely would not do any
of these replacements, the only reason we have not seen this
break yet is probably that rewriteStrings is only called for
store paths and things that look like store paths (and those
should never overlap nor admit such transitive replacements)

Change-Id: I6fc29f939d5061d9f56c752624a823ece8437c07

1 files changed, 39 insertions, 0 deletions

diff --git a/tests/unit/libutil/tests.cc b/tests/unit/libutil/tests.cc
index f55c56548..720370066 100644
--- a/tests/unit/libutil/tests.cc
+++ b/tests/unit/libutil/tests.cc
@@ -404,6 +404,45 @@ namespace nix {
         ASSERT_EQ(rewriteStrings("this and that", rewrites), "that and that");
     }
 
+    TEST(rewriteStrings, intransitive) {
+        StringMap rewrites;
+        // transitivity can happen both in forward and reverse iteration order of the rewrite map.
+        rewrites["a"] = "b";
+        rewrites["b"] = "c";
+        rewrites["e"] = "b";
+
+        ASSERT_EQ(rewriteStrings("abcde", rewrites), "bccdb");
+    }
+
+    TEST(rewriteStrings, nonoverlapping) {
+        StringMap rewrites;
+        rewrites["ab"] = "ca";
+
+        ASSERT_EQ(rewriteStrings("abb", rewrites), "cab");
+    }
+
+    TEST(rewriteStrings, differentLength) {
+        StringMap rewrites;
+        rewrites["a"] = "an has a trea";
+
+        ASSERT_EQ(rewriteStrings("cat", rewrites), "can has a treat");
+    }
+
+    TEST(rewriteStrings, sorted) {
+        StringMap rewrites;
+        rewrites["a"] = "meow";
+        rewrites["abc"] = "puppy";
+
+        ASSERT_EQ(rewriteStrings("abcde", rewrites), "meowbcde");
+    }
+
+    TEST(rewriteStrings, multiple) {
+        StringMap rewrites;
+        rewrites["a"] = "b";
+
+        ASSERT_EQ(rewriteStrings("a1a2a3a", rewrites), "b1b2b3b");
+    }
+
     TEST(rewriteStrings, doesntOccur) {
         StringMap rewrites;
         rewrites["foo"] = "bar";