Merge pull request #9747 from awakesecurity/mz/fix-quadratic-splitString

Fix performance of builtins.substring for empty substrings

(cherry picked from commit b2deff1947c2fe57fdbf1a472eb9003eb407f8d3)
Change-Id: I4ddfc8d26a4781c9520fff9807849a073ee7bed8

1 files changed, 16 insertions, 3 deletions

diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index e107db228..d64f2d51e 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -3700,9 +3700,6 @@ static RegisterPrimOp primop_toString({
 static void prim_substring(EvalState & state, const PosIdx pos, Value * * args, Value & v)
 {
     int start = state.forceInt(*args[0], pos, "while evaluating the first argument (the start offset) passed to builtins.substring");
-    int len = state.forceInt(*args[1], pos, "while evaluating the second argument (the substring length) passed to builtins.substring");
-    NixStringContext context;
-    auto s = state.coerceToString(pos, *args[2], context, "while evaluating the third argument (the string) passed to builtins.substring");
 
     if (start < 0)
         state.debugThrowLastTrace(EvalError({
@@ -3710,6 +3707,22 @@ static void prim_substring(EvalState & state, const PosIdx pos, Value * * args,
             .errPos = state.positions[pos]
         }));
 
+
+    int len = state.forceInt(*args[1], pos, "while evaluating the second argument (the substring length) passed to builtins.substring");
+
+    // Special-case on empty substring to avoid O(n) strlen
+    // This allows for the use of empty substrings to efficently capture string context
+    if (len == 0) {
+        state.forceValue(*args[2], pos);
+        if (args[2]->type() == nString) {
+            v.mkString("", args[2]->string.context);
+            return;
+        }
+    }
+
+    NixStringContext context;
+    auto s = state.coerceToString(pos, *args[2], context, "while evaluating the third argument (the string) passed to builtins.substring");
+
     v.mkString((unsigned int) start >= s->size() ? "" : s->substr(start, len), context);
 }