[libc] Add strstr implementation.

[cgyurgyik]

Summary

[libc] Adds a simple strstr implementation as well as unit tests. This will be improved in follow-up revisions.

[sivachandra]

libc/src/string/strstr.cpp

17

You shouldn't need strlen even for a brute force implementation unless a future update will call strlen. Even then, doesn't seem like using strlen should be used until we really need it.

25

This declaration can be moved within the outer for loop?

[cgyurgyik]

libc/src/string/strstr.cpp

17

You're right. Fixed, thanks.

[sivachandra]

libc/src/string/strstr.cpp

17

Nitty comment on a comment: Remove (and will) :)

libc/config/linux/aarch64/entrypoints.txt

 set(TARGET_LIBC_ENTRYPOINTS
     # errno.h entrypoints
     libc.src.errno.__errno_location
 
     # string.h entrypoints
     libc.src.string.bzero
     libc.src.string.memcpy
     libc.src.string.memset
     libc.src.string.strcpy
     libc.src.string.strcat
     libc.src.string.strlen
     libc.src.string.memchr
     libc.src.string.strchr
+    libc.str.string.strstr
 )
 
 set(TARGET_LIBM_ENTRYPOINTS
     # math.h entrypoints
     libc.src.math.copysign
     libc.src.math.copysignf
     libc.src.math.copysignl
     libc.src.math.ceil

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.memcpy
     libc.src.string.memset
     libc.src.string.strcpy
     libc.src.string.strcat
     libc.src.string.strlen
     libc.src.string.strcmp
     libc.src.string.memchr
     libc.src.string.strchr
+    libc.src.string.strstr
 
     # sys/mman.h entrypoints
     libc.src.sys.mman.mmap
     libc.src.sys.mman.munmap
 
     # threads.h entrypoints
     libc.src.threads.call_once
     libc.src.threads.mtx_init

libc/src/string/CMakeLists.txt

 add_entrypoint_object(
   strchr
   SRCS
     strchr.cpp
   HDRS
     strchr.h
 )
 
+add_entrypoint_object(
+  strstr
+  SRCS
+    strstr.cpp
+  HDRS
+    strstr.h
+  DEPENDS
+    .strlen
+)
+
 # Helper to define a function with multiple implementations
 # - Computes flags to satisfy required/rejected features and arch,
 # - Declares an entry point,
 # - Attach the REQUIRE_CPU_FEATURES property to the target,
 # - Add the fully qualified target to `${name}_implementations` global property for tests.
 function(add_implementation name impl_name)
   cmake_parse_arguments(
     "ADD_IMPL"

libc/src/string/strstr.h

+//===-- Implementation header for strstr ------------------------*- 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_STRSTR_H
+#define LLVM_LIBC_SRC_STRING_STRSTR_H
+
+namespace __llvm_libc {
+
+char *strstr(const char *haystack, const char *needle);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_STRSTR_H

libc/src/string/strstr.cpp

+//===-- Implementation of strstr ------------------------------------------===//
+//
+// 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/strstr.h"
+
+#include "src/__support/common.h"
+#include "src/string/strlen.h"
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+// TODO: This is a simple brute force implementation that uses strlen.
+// This can (and will) be improved upon using well known string matching
+// algorithms such as Boyer-Moore.
+char *LLVM_LIBC_ENTRYPOINT(strstr)(const char *haystack, const char *needle) {
+  const size_t hsize = strlen(haystack);
+  const size_t nsize = strlen(needle);
+  if (nsize > hsize)
+    return nullptr;
+  size_t j;
+  for (size_t i = 0; i <= hsize - nsize; ++i) {
+    for (j = 0; j < nsize && haystack[i + j] == needle[j]; ++j)
+      ;
+    if (j == nsize)
+      return const_cast<char *>(haystack + i);
+  }
+  return nullptr;
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_string_unittests
   SRCS
     strchr_test.cpp
   DEPENDS
     libc.src.string.strchr
 )
 
+add_libc_unittest(
+  strstr_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    strstr_test.cpp
+  DEPENDS
+    libc.src.string.strstr
+)
+
 # Tests all implementations that can run on the host.
 function(add_libc_multi_impl_test name)
   get_property(fq_implementations GLOBAL PROPERTY ${name}_implementations)
   foreach(fq_config_name IN LISTS fq_implementations)
     get_target_property(required_cpu_features ${fq_config_name} REQUIRE_CPU_FEATURES)
     host_supports(can_run "${required_cpu_features}")
     if(can_run)
       add_libc_unittest(

libc/test/src/string/strstr_test.cpp

+//===-- Unittests for strstr ----------------------------------------------===//
+//
+// 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/strstr.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(StrStrTest, NeedleNotInHaystack) {
+  const char *haystack = "12345";
+  const char *needle = "a";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), nullptr);
+}
+
+TEST(StrStrTest, NeedleIsEmptyString) {
+  const char *haystack = "12345";
+  const char *needle = "";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), haystack);
+}
+
+TEST(StrStrTest, HaystackIsEmptyString) {
+  const char *haystack = "";
+  const char *needle = "12345";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), nullptr);
+}
+
+TEST(StrStrTest, HaystackAndNeedleAreEmptyStrings) {
+  const char *haystack = "";
+  const char *needle = "";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "");
+}
+
+TEST(StrStrTest, HaystackAndNeedleAreSingleCharacters) {
+  const char *haystack = "a";
+  // Same characer returns that character.
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, /*needle=*/"a"), "a");
+  // Different character returns nullptr.
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, /*needle=*/"b"), nullptr);
+}
+
+TEST(StrStrTest, NeedleEqualToHaystack) {
+  const char *haystack = "12345";
+  const char *needle = "12345";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "12345");
+}
+
+TEST(StrStrTest, NeedleSmallerThanHaystack) {
+  const char *haystack = "12345";
+  const char *needle = "345";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "345");
+}
+
+TEST(StrStrTest, NeedleLargerThanHaystack) {
+  const char *haystack = "123";
+  const char *needle = "12345";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), nullptr);
+}
+
+TEST(StrStrTest, NeedleAtBeginning) {
+  const char *haystack = "12345";
+  const char *needle = "12";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "12345");
+}
+
+TEST(StrStrTest, NeedleInMiddle) {
+  const char *haystack = "abcdefghi";
+  const char *needle = "def";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "defghi");
+}
+
+TEST(StrStrTest, NeedleDirectlyBeforeNullTerminator) {
+  const char *haystack = "abcdefghi";
+  const char *needle = "ghi";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "ghi");
+}
+
+TEST(StrStrTest, NeedlePastNullTerminator) {
+  const char haystack[5] = {'1', '2', '\0', '3', '4'};
+  // Shouldn't find anything after the null terminator.
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, /*needle=*/"3"), nullptr);
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, /*needle=*/"4"), nullptr);
+}
+
+TEST(StrStrTest, PartialNeedle) {
+  const char *haystack = "la_ap_lap";
+  const char *needle = "lap";
+  // Shouldn't find la or ap.
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "lap");
+}
+
+TEST(StrStrTest, MisspelledNeedle) {
+  const char *haystack = "atalloftwocities...wait, tale";
+  const char *needle = "tale";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "tale");
+}
+
+TEST(StrStrTest, AnagramNeedle) {
+  const char *haystack = "dgo_ogd_god_odg_gdo_dog";
+  const char *needle = "dog";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, needle), "dog");
+}
+
+TEST(StrStrTest, MorphedNeedle) {
+  // Changes a single letter in the needle to mismatch with the haystack.
+  const char *haystack = "once upon a time";
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, "time"), "time");
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, "lime"), nullptr);
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, "tome"), nullptr);
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, "tire"), nullptr);
+  ASSERT_STREQ(__llvm_libc::strstr(haystack, "timo"), nullptr);
+}