fix #19500; remove find optimization [backport: 1.6] (#19714)

* remove find optimization

close #19500

* save find to std

* add simple tests

* Apply suggestions from code review

Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>

Co-authored-by: sandytypical <43030857+xflywind@users.noreply.github.com>
Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>

4 files changed, 49 insertions, 20 deletions

diff --git a/lib/pure/strutils.nim b/lib/pure/strutils.nim
index 3ae953a55..b6c0d6917 100644
--- a/lib/pure/strutils.nim
+++ b/lib/pure/strutils.nim
@@ -1882,9 +1882,6 @@ func find*(a: SkipTable, s, sub: string, start: Natural = 0, last = -1): int {.
 when not (defined(js) or defined(nimdoc) or defined(nimscript)):
   func c_memchr(cstr: pointer, c: char, n: csize_t): pointer {.
                 importc: "memchr", header: "<string.h>".}
-  func c_strstr(haystack, needle: cstring): cstring {.
-    importc: "strstr", header: "<string.h>".}
-
   const hasCStringBuiltin = true
 else:
   const hasCStringBuiltin = false
@@ -1954,23 +1951,7 @@ func find*(s, sub: string, start: Natural = 0, last = -1): int {.rtl,
   if sub.len > s.len - start: return -1
   if sub.len == 1: return find(s, sub[0], start, last)
 
-  template useSkipTable =
-    result = find(initSkipTable(sub), s, sub, start, last)
-
-  when nimvm:
-    useSkipTable()
-  else:
-    when hasCStringBuiltin:
-      if last < 0 and start < s.len:
-        let found = c_strstr(s[start].unsafeAddr, sub)
-        result = if not found.isNil:
-            cast[ByteAddress](found) -% cast[ByteAddress](s.cstring)
-          else:
-            -1
-      else:
-        useSkipTable()
-    else:
-      useSkipTable()
+  result = find(initSkipTable(sub), s, sub, start, last)
 
 func rfind*(s: string, sub: char, start: Natural = 0, last = -1): int {.rtl,
     extern: "nsuRFindChar".} =
diff --git a/lib/std/private/strimpl.nim b/lib/std/private/strimpl.nim
index 7d42a7cf8..7d19825f4 100644
--- a/lib/std/private/strimpl.nim
+++ b/lib/std/private/strimpl.nim
@@ -74,3 +74,40 @@ template endsWithImpl*[T: string | cstring](s, suffix: T) =
 
 func cmpNimIdentifier*[T: string | cstring](a, b: T): int =
   cmpIgnoreStyleImpl(a, b, true)
+
+func c_memchr(cstr: pointer, c: char, n: csize_t): pointer {.
+              importc: "memchr", header: "<string.h>".}
+func c_strstr(haystack, needle: cstring): cstring {.
+  importc: "strstr", header: "<string.h>".}
+
+
+func find*(s: cstring, sub: char, start: Natural = 0, last = 0): int =
+  ## Searches for `sub` in `s` inside the range `start..last` (both ends included).
+  ## If `last` is unspecified, it defaults to `s.high` (the last element).
+  ##
+  ## Searching is case-sensitive. If `sub` is not in `s`, -1 is returned.
+  ## Otherwise the index returned is relative to `s[0]`, not `start`.
+  ## Use `s[start..last].rfind` for a `start`-origin index.
+  let last = if last == 0: s.high else: last
+  let L = last-start+1
+  if L > 0:
+    let found = c_memchr(s[start].unsafeAddr, sub, cast[csize_t](L))
+    if not found.isNil:
+      return cast[ByteAddress](found) -% cast[ByteAddress](s)
+  return -1
+
+func find*(s, sub: cstring, start: Natural = 0, last = 0): int =
+  ## Searches for `sub` in `s` inside the range `start..last` (both ends included).
+  ## If `last` is unspecified, it defaults to `s.high` (the last element).
+  ##
+  ## Searching is case-sensitive. If `sub` is not in `s`, -1 is returned.
+  ## Otherwise the index returned is relative to `s[0]`, not `start`.
+  ## Use `s[start..last].find` for a `start`-origin index.
+  if sub.len > s.len - start: return -1
+  if sub.len == 1: return find(s, sub[0], start, last)
+  if last == 0 and s.len > start:
+    let found = c_strstr(s[start].unsafeAddr, sub)
+    if not found.isNil:
+      result = cast[ByteAddress](found) -% cast[ByteAddress](s)
+    else:
+      result = -1
diff --git a/tests/stdlib/tstrimpl.nim b/tests/stdlib/tstrimpl.nim
new file mode 100644
index 000000000..4d0ef827f
--- /dev/null
+++ b/tests/stdlib/tstrimpl.nim
@@ -0,0 +1,6 @@
+import std/private/strimpl
+
+doAssert find(cstring"Hello Nim", cstring"Nim") == 6
+doAssert find(cstring"Hello Nim", cstring"N") == 6
+doAssert find(cstring"Hello Nim", cstring"I") == -1
+doAssert find(cstring"Hello Nim", cstring"O") == -1
diff --git a/tests/stdlib/tstrutils.nim b/tests/stdlib/tstrutils.nim
index 0e6384d7e..32929ef17 100644
--- a/tests/stdlib/tstrutils.nim
+++ b/tests/stdlib/tstrutils.nim
@@ -868,5 +868,10 @@ bar
     doAssert nimIdentNormalize("Foo_bar") == "Foobar"
     doAssert nimIdentNormalize("_Foo_bar") == "_foobar"
 
+  block: # bug #19500
+    doAssert "abc \0 def".find("def") == 6
+    doAssert "abc \0 def".find('d') == 6
+
+
 static: main()
 main()