[libc] Add memmem implementation

[Caslyn]

Summary

Introduce the memmem libc string function.

memmem_implementation performs shared logic for strstr,
strcasestr, and memmem; essentially reconfiguring what was the
strstr_implementation to support length parameters.

[Caslyn]

Fix typo

[michaelrj]

Code looks good to me, I've added @gchatelet for his opinion on memmem being in memory_utils.

libc/src/string/memmem.cpp

1

nit: typo

[mcgrathr]

libc/src/string/memory_utils/strstr_implementations.h

17

It might make sense to keep this around and still call it from strstr, even if strstr_implementation just calls memmem_implementation. An optimized strstr might roll the length determination into the search more efficiently than strlen+memmem so it doesn't seem ideal to have the public entrypoint code assume that strlen+memmem is the implementation you want.

[Caslyn]

Fix typos

[Caslyn]

Add back strstr_implementations to call memmmem_implementation.

[Caslyn]

libc/src/string/memory_utils/strstr_implementations.h

17

That makes sense - thanks for pointing out.

[Caslyn]

In D147822#4255905, @michaelrj wrote:

Code looks good to me, I've added @gchatelet for his opinion on memmem being in memory_utils.

There's a bit of urgency to have this merged so we can begin some testing on Fuchsia, @gchatelet would appreciate your review as soon as you can.

[mcgrathr]

LGTM. We can look into any possible code-sharing with strstr_implementation later along with optimization.

libc/src/string/memmem.cpp

19

Can be constexpr.

[gchatelet]

Sorry for the lag, Monday was off in France and I missed the patch today.
I'm not blocking this patch but please consider the suggested changes.

libc/src/string/memory_utils/memmem_implementations.h

19

Not necessarily for this patch but it may be better to use the cpp::string_view abstraction for both needle and haystack.

We should also return a const char* to keep types as sane as possible.
This way we const_cast only where it actually matters, i.e. in memmem.

libc/test/src/string/memmem_test.cpp

82

put on a single line

98

same here

[mcgrathr]

In D147822#4259080, @gchatelet wrote:

Sorry for the lag, Monday was off in France and I missed the patch today.
I'm not blocking this patch but please consider the suggested changes.

These are good suggestions and easy to apply right away before landing.

libc/test/src/string/memmem_test.cpp

98

Note that clang-format will use separate lines for each element when there is a trailing comma before the end-brace, and will compact things when there is no trailing comma.

[mcgrathr]

libc/src/string/memmem.cpp

19

If this is intended as an ordering comparison and not just equality, then generally unsigned char should be used.

[Caslyn]

Updates to memmem.cpp/memmem_test.cpp per review feedback

[Caslyn]

Thanks for the quick response @gchatelet!

libc/src/string/memory_utils/memmem_implementations.h

19

I'll be sure to address this in a follow up patch.

libc/test/src/string/memmem_test.cpp

98

Ah - thanks. I noticed this behavior with clang-format but wasn't sure how to work around it. Done.

libc/config/baremetal/arm/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     # string.h entrypoints
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp
     libc.src.string.strcasestr

libc/config/darwin/arm/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     # string.h entrypoints
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp
     libc.src.string.strcasestr

libc/config/darwin/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     
     # string.h entrypoints
     libc.src.string.bcmp
     libc.src.string.bzero
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcat
     libc.src.string.strchr

libc/config/gpu/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
 
     # string.h entrypoints
     libc.src.string.bcmp
     libc.src.string.bzero
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp
     libc.src.string.strcasestr

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.index
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.rindex
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp

libc/config/linux/arm/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.index
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.rindex
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp

libc/config/linux/riscv64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.index
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.rindex
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.index
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.rindex
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp

libc/config/windows/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     # string.h entrypoints
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmem
     libc.src.string.memmove
     libc.src.string.mempcpy
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.stpcpy
     libc.src.string.stpncpy
     libc.src.string.strcasecmp
     libc.src.string.strcasestr

libc/spec/gnu_ext.td

HeaderSpec Sched = HeaderSpec<
       ]
   >;
  
   HeaderSpec String = HeaderSpec<
       "string.h",
       [], // Macros
       [], // Types
       [], // Enumerations
-      [ 
+      [
          FunctionSpec<
+            "memmem",
+            RetValSpec<VoidPtr>,
+            [ArgSpec<ConstVoidPtr>, ArgSpec<SizeTType>, ArgSpec<ConstVoidPtr>, ArgSpec<SizeTType]
+        >,
+        FunctionSpec<
             "memrchr",
             RetValSpec<VoidPtr>,
             [ArgSpec<VoidPtr>, ArgSpec<IntType>, ArgSpec<SizeTType>]
         >,
         FunctionSpec<
             "strerror_r",
             RetValSpec<CharPtr>,
             [ArgSpec<IntType>, ArgSpec<CharPtr>, ArgSpec<SizeTType>]

libc/src/string/CMakeLists.txt

SRCS
     mempcpy.cpp
   HDRS
     mempcpy.h
   DEPENDS
     .memory_utils.memcpy_implementation
 )
 
 add_entrypoint_object(
+  memmem
+  SRCS
+    memmem.cpp
+  HDRS
+    memmem.h
+  DEPENDS
+    .memory_utils.memmem_implementation
+)
+
+add_entrypoint_object(
   memchr
   SRCS
     memchr.cpp
   HDRS
     memchr.h
   DEPENDS
     .string_utils
 )

libc/src/string/memmem.h

+//===-- Implementation header for memmem ------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STRING_MEMMEM_H
+#define LLVM_LIBC_SRC_STRING_MEMMEM_H
+
+#include <stddef.h> // For size_t
+
+namespace __llvm_libc {
+
+void *memmem(const void *haystack, size_t haystack_len, const void *needle,
+             size_t needle_len);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMMEM_H

libc/src/string/memmem.cpp

+//===-- Implementation of memmem ------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/string/memmem.h"
+#include "src/__support/common.h"
+#include "src/string/memory_utils/memmem_implementations.h"
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(void *, memmem,
+                   (const void *haystack, size_t haystack_len,
+                    const void *needle, size_t needle_len)) {
+  constexpr auto comp = [](unsigned char l, unsigned char r) -> int {
+    return l - r;
+  };
+  return memmem_implementation(haystack, haystack_len, needle, needle_len,
+                               comp);
+}
+
+} // namespace __llvm_libc

libc/src/string/memory_utils/CMakeLists.txt

 
 add_header_library(
   strcmp_implementation
   HDRS
     strcmp_implementations.h
 )
 
 add_header_library(
-  strstr_implementation
   HDRS
     strstr_implementations.h
 )
+
+add_header_library(
+  memmem_implementation
+  HDRS
+    memmem_implementations.h
+)

libc/src/string/memory_utils/memmem_implementations.h

+//===-- memmem implementation -----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMMEM_IMPLEMENTATIONS_H
+#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMMEM_IMPLEMENTATIONS_H
+
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+template <typename Comp>
+constexpr static void *
+memmem_implementation(const void *haystack, size_t haystack_len,
+                      const void *needle, size_t needle_len, Comp &&comp) {
+  // TODO: simple brute force implementation. This can be
+  // improved upon using well known string matching algorithms.
+  if (!needle_len)
+    return const_cast<void *>(haystack);
+
+  if (needle_len > haystack_len)
+    return nullptr;
+
+  const unsigned char *h = static_cast<const unsigned char *>(haystack);
+  const unsigned char *n = static_cast<const unsigned char *>(needle);
+  for (size_t i = 0; i <= (haystack_len - needle_len); ++i) {
+    size_t j = 0;
+    for (; j < needle_len && !comp(h[i + j], n[j]); ++j)
+      ;
+    if (j == needle_len)
+      return const_cast<unsigned char *>(h + i);
+  }
+  return nullptr;
+}
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_MEMMEM_IMPLEMENTATIONS_H

libc/src/string/memory_utils/strstr_implementations.h

 //===-- str{,case}str implementation ----------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_STRSTR_IMPLEMENTATIONS_H
 #define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_STRSTR_IMPLEMENTATIONS_H
 
+#include "src/string/memory_utils/memmem_implementations.h"
+#include "src/string/string_utils.h"
 #include <stddef.h>
 
 namespace __llvm_libc {
 
 template <typename Comp>
 constexpr static char *strstr_implementation(const char *haystack,
                                              const char *needle, Comp &&comp) {
-  // TODO: This is a simple brute force implementation. This can be
-  // improved upon using well known string matching algorithms.
-  for (size_t i = 0; comp(haystack[i], 0); ++i) {
-    size_t j = 0;
-    for (; comp(haystack[i + j], 0) && !comp(haystack[i + j], needle[j]); ++j)
-      ;
-    if (!comp(needle[j], 0))
-      return const_cast<char *>(haystack + i);
-  }
-  return nullptr;
+  void *result = memmem_implementation(
+      static_cast<const void *>(haystack), internal::string_length(haystack),
+      static_cast<const void *>(needle), internal::string_length(needle), comp);
+  return static_cast<char *>(result);
 }
 
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_STRSTR_IMPLEMENTATIONS_H

libc/test/src/string/CMakeLists.txt

SUITE
     libc_string_unittests
   SRCS
     mempcpy_test.cpp
   DEPENDS
     libc.src.string.mempcpy
 )
 
 add_libc_unittest(
+  memmem_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    memmem_test.cpp
+  DEPENDS
+    libc.src.string.memmem
+)
+
+add_libc_unittest(
   memchr_test
   SUITE
     libc_string_unittests
   SRCS
     memchr_test.cpp
   DEPENDS
     libc.src.string.memchr
 )

libc/test/src/string/memmem_test.cpp

+//===-- Unittests for memmem ----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/string/memmem.h"
+#include "test/UnitTest/Test.h"
+
+#include "src/string/string_utils.h"
+
+namespace __llvm_libc {
+
+TEST(LlvmLibcMemmemTest, EmptyHaystackEmptyNeedleReturnsHaystck) {
+  char *h = nullptr;
+  char *n = nullptr;
+  void *result = __llvm_libc::memmem(h, 0, n, 0);
+  ASSERT_EQ(static_cast<char *>(result), h);
+}
+
+TEST(LlvmLibcMemmemTest, EmptyHaystackNonEmptyNeedleReturnsNull) {
+  char *h = nullptr;
+  char n[] = {'a', 'b', 'c'};
+  void *result = __llvm_libc::memmem(h, 0, n, sizeof(n));
+  ASSERT_EQ(result, static_cast<void *>(nullptr));
+}
+
+TEST(LlvmLibcMemmemTest, EmptyNeedleReturnsHaystack) {
+  char h[] = {'a', 'b', 'c'};
+  char *n = nullptr;
+  void *result = __llvm_libc::memmem(h, sizeof(h), n, 0);
+  ASSERT_EQ(static_cast<char *>(result), h);
+}
+
+TEST(LlvmLibcMemmemTest, ExactMatchReturnsHaystack) {
+  char h[] = {'a', 'b', 'c'};
+  char n[] = {'a', 'b', 'c'};
+  void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+  ASSERT_EQ(static_cast<char *>(result), h);
+}
+
+TEST(LlvmLibcMemmemTest, ReturnFirstMatchOfNeedle) {
+  char h[] = {'a', 'a', 'b', 'c'};
+  char n[] = {'a'};
+  void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+  ASSERT_EQ(static_cast<char *>(result), h);
+}
+
+TEST(LlvmLibcMemmemTest, ReturnFirstExactMatchOfNeedle) {
+  {
+    char h[] = {'a', 'b', 'a', 'c', 'a', 'a'};
+    char n[] = {'a', 'a'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+    ASSERT_EQ(static_cast<char *>(result), h + 4);
+  }
+  {
+    char h[] = {'a', 'a', 'b', 'a', 'b', 'a'};
+    char n[] = {'a', 'b', 'a'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+    ASSERT_EQ(static_cast<char *>(result), h + 1);
+  }
+}
+
+TEST(LlvmLibcMemmemTest, NullTerminatorDoesNotInterruptMatch) {
+  char h[] = {'\0', 'a', 'b'};
+  char n[] = {'a', 'b'};
+  void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+  ASSERT_EQ(static_cast<char *>(result), h + 1);
+}
+
+TEST(LlvmLibcMemmemTest, ReturnNullIfNoExactMatch) {
+  {
+    char h[] = {'a'};
+    char n[] = {'a', 'a'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+    ASSERT_EQ(result, static_cast<void *>(nullptr));
+  }
+  {
+    char h[] = {'a', 'A'};
+    char n[] = {'a', 'a'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+    ASSERT_EQ(result, static_cast<void *>(nullptr));
+  }
+  {
+    char h[] = {'a'};
+    char n[] = {'a', '\0'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+    ASSERT_EQ(result, static_cast<void *>(nullptr));
+  }
+  {
+    char h[] = {'\0'};
+    char n[] = {'\0', '\0'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, sizeof(n));
+    ASSERT_EQ(result, static_cast<void *>(nullptr));
+  }
+}
+
+TEST(LlvmLibcMemmemTest, ReturnMatchOfSpecifiedNeedleLength) {
+  {
+    char h[] = {'a', 'b', 'c'};
+    char n[] = {'x', 'y', 'z'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, 0);
+    ASSERT_EQ(static_cast<char *>(result), h);
+  }
+  {
+    char h[] = {'a', 'b', 'c'};
+    char n[] = {'b', 'c', 'a'};
+    void *result = __llvm_libc::memmem(h, sizeof(h), n, 2);
+    ASSERT_EQ(static_cast<char *>(result), h + 1);
+  }
+}
+
+TEST(LlvmLibcMemmemTest, ReturnNullIfInadequateHaystackLength) {
+  {
+    char h[] = {'a', 'b', 'c'};
+    char n[] = {'c'};
+    void *result = __llvm_libc::memmem(h, 2, n, sizeof(n));
+    ASSERT_EQ(result, static_cast<void *>(nullptr));
+  }
+  {
+    char h[] = {'a', 'b', 'c'};
+    char n[] = {'a', 'b', 'c'};
+    void *result = __llvm_libc::memmem(h, 2, n, sizeof(n));
+    ASSERT_EQ(result, static_cast<void *>(nullptr));
+  }
+}
+} // namespace __llvm_libc

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

textual_hdrs = [
         "src/string/memory_utils/bcmp_implementations.h",
         "src/string/memory_utils/bzero_implementations.h",
         "src/string/memory_utils/memcmp_implementations.h",
         "src/string/memory_utils/memcpy_implementations.h",
         "src/string/memory_utils/memmove_implementations.h",
         "src/string/memory_utils/memset_implementations.h",
         "src/string/memory_utils/strcmp_implementations.h",
         "src/string/memory_utils/strstr_implementations.h",
+        "src/string/memory_utils/memmem_implementations.h",
         "src/string/memory_utils/x86_64/memcmp_implementations.h",
         "src/string/memory_utils/x86_64/memcpy_implementations.h",
     ],
     deps = [
         ":__support_common",
         ":__support_cpp_array",
         ":__support_cpp_bit",
         ":__support_cpp_cstddef",