[libc] Add strtok implementation.

[cgyurgyik]

Summary

Rationale: Calling strspn and strcspn in strtok would currently create two separate Bitset instances and loop through the delimiters twice. We can avoid this by creating one instance inside the strtok function.

Also removes unnecessary header from String utils.

[sivachandra]

libc/src/string/strtok.cpp

17

Nit: delimiter_string

18

Nit: delimiter_set

22

Nit: Can you move this out side of this function and call it strtok_str?

24

I think the comments are reversed. It should be "non-delimiter" here and "delimiter" below? But, I think comments are just a distraction here as the code speaks for itself.

28

Nit: s/delimiter_span/token

34

A readability thing to not mix increment/decrement operators with other operators:

*strtok_str = '\0';
 ++strtok_str;

libc/test/src/string/strtok_test.cpp

62

Does strtok as implemented above ever return nullptr? This got me to go look why ASSERT_STREQ is happy. It turns out, our STREQ comparison first converts the string to llvm::StringRef which makes an empty string compare equal to a nullptr! That needs fixing separately.

[cgyurgyik]

libc/test/src/string/strtok_test.cpp

62

Do we want strtok to return nullptr in the case the null terminator is hit?

[cgyurgyik]

Address Siva's comments.

[sivachandra]

libc/test/src/string/strtok_test.cpp

62

Yes. I would think that is what this text from the standard means:

If no such character was found, there are no tokens in str at all, and the function returns a null pointer.

https://en.cppreference.com/w/c/string/byte/strtok

[cgyurgyik]

Address comment.

[sivachandra]

libc/src/string/strtok.cpp

27

Should we update strtok_str = src ?

libc/test/src/string/strtok_test.cpp

62

Switch this to ASSERT_EQ?

66

Same here.

78

And here.

[cgyurgyik]

libc/test/src/string/strtok_test.cpp

62

I get:

 no matching function for call to 'test'
  ASSERT_EQ(token, nullptr);
...
template ignored: deduced conflicting types for parameter 'ValType' ('char *' vs. 'nullptr_t')
  static bool test(RunContext &Ctx, TestCondition Cond, ValType LHS,

Is there an easy fix for this that I'm missing?

[sivachandra]

libc/test/src/string/strtok_test.cpp

62

Never mind then. I will fix it separately.

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.strcpy
     libc.src.string.strcspn
     libc.src.string.strlen
     libc.src.string.strnlen
     libc.src.string.strpbrk
     libc.src.string.strrchr
     libc.src.string.strspn
     libc.src.string.strstr
+    libc.src.string.strtok
 )
 
 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.strcpy
     libc.src.string.strcspn
     libc.src.string.strlen
     libc.src.string.strnlen
     libc.src.string.strpbrk
     libc.src.string.strrchr
     libc.src.string.strspn
     libc.src.string.strstr
+    libc.src.string.strtok
 
     # 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(
   SRCS
     strpbrk.cpp
   HDRS
     strpbrk.h
   DEPENDS
     .string_utils
 )
 
+add_entrypoint_object(
+  strtok
+  SRCS
+    strtok.cpp
+  HDRS
+    strtok.h
+  DEPENDS
+    libc.utils.CPP.standalone_cpp
+)
+
 # 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/string_utils.h

 //===-- String utils --------------------------------------------*- 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 LIBC_SRC_STRING_STRING_UTILS_H
 #define LIBC_SRC_STRING_STRING_UTILS_H
 
-#include "src/string/memory_utils/utils.h"
-
 #include "utils/CPP/Bitset.h"
 #include <stddef.h> // size_t
 
 namespace __llvm_libc {
 namespace internal {
 
 // Returns the maximum length span that contains only characters not found in
 // 'segment'. If no characters are found, returns the length of 'src'.

libc/src/string/strtok.h

+//===-- Implementation header for strtok ------------------------*- 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_STRTOK_H
+#define LLVM_LIBC_SRC_STRING_STRTOK_H
+
+namespace __llvm_libc {
+
+char *strtok(char *src, const char *delimiter_string);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_STRTOK_H

libc/src/string/strtok.cpp

+//===-- Implementation of strtok ------------------------------------------===//
+//
+// 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/strtok.h"
+
+#include "src/__support/common.h"
+#include "utils/CPP/Bitset.h"
+
+namespace __llvm_libc {
+
+static char *strtok_str = nullptr;
+
+char *LLVM_LIBC_ENTRYPOINT(strtok)(char *src, const char *delimiter_string) {
+  cpp::Bitset<256> delimiter_set;
+  for (; *delimiter_string; ++delimiter_string)
+    delimiter_set.set(*delimiter_string);
+
+  src = src ? src : strtok_str;
+  for (; *src && delimiter_set.test(*src); ++src)
+    ;
+  if (!*src) {
+    strtok_str = src;
+    return nullptr;
+  }
+  char *token = src;
+  for (; *src && !delimiter_set.test(*src); ++src)
+    ;
+
+  strtok_str = src;
+  if (*strtok_str) {
+    *strtok_str = '\0';
+    ++strtok_str;
+  }
+  return token;
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_string_unittests
   SRCS
     strpbrk_test.cpp
   DEPENDS
     libc.src.string.strpbrk
 )
 
+add_libc_unittest(
+  strtok_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    strtok_test.cpp
+  DEPENDS
+    libc.src.string.strtok
+)
+
 # 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/strtok_test.cpp

+//===-- Unittests for strtok ---------------------------------------------===//
+//
+// 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/strtok.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(StrTokTest, NoTokenFound) {
+  char empty[] = "";
+  ASSERT_STREQ(__llvm_libc::strtok(empty, ""), nullptr);
+  ASSERT_STREQ(__llvm_libc::strtok(empty, "_"), nullptr);
+
+  char single[] = "_";
+  ASSERT_STREQ(__llvm_libc::strtok(single, ""), "_");
+
+  char multiple[] = "1,2";
+  ASSERT_STREQ(__llvm_libc::strtok(multiple, ":"), "1,2");
+}
+
+TEST(StrTokTest, DelimiterAsFirstCharacterShouldBeIgnored) {
+  char src[] = ".123";
+  ASSERT_STREQ(__llvm_libc::strtok(src, "."), "123");
+}
+
+TEST(StrTokTest, DelimiterIsMiddleCharacter) {
+  char src[] = "12,34";
+  ASSERT_STREQ(__llvm_libc::strtok(src, ","), "12");
+}
+
+TEST(StrTokTest, DelimiterAsLastCharacterShouldBeIgnored) {
+  char src[] = "1234:";
+  ASSERT_STREQ(__llvm_libc::strtok(src, ":"), "1234");
+}
+
+TEST(StrTokTest, MultipleDelimiters) {
+  char src[] = "12,.34";
+  ASSERT_STREQ(__llvm_libc::strtok(src, "."), "12,");
+  ASSERT_STREQ(__llvm_libc::strtok(src, ".,"), "12");
+  ASSERT_STREQ(__llvm_libc::strtok(src, ",."), "12");
+  ASSERT_STREQ(__llvm_libc::strtok(src, ":,."), "12");
+}
+
+TEST(StrTokTest, ShouldNotGoPastNullTerminator) {
+  char src[] = {'1', '2', '\0', ',', '3'};
+  ASSERT_STREQ(__llvm_libc::strtok(src, ","), "12");
+}
+
+TEST(StrTokTest, SubsequentCallsShouldFindFollowingDelimiters) {
+  char src[] = "12,34.56";
+  char *token = __llvm_libc::strtok(src, ",.");
+  ASSERT_STREQ(token, "12");
+  token = __llvm_libc::strtok(nullptr, ",.");
+  ASSERT_STREQ(token, "34");
+  token = __llvm_libc::strtok(nullptr, ",.");
+  ASSERT_STREQ(token, "56");
+  token = __llvm_libc::strtok(nullptr, "_:,_");
+  ASSERT_STREQ(token, nullptr);
+  // Subsequent calls after hitting the end of the string should also return
+  // nullptr.
+  token = __llvm_libc::strtok(nullptr, "_:,_");
+  ASSERT_STREQ(token, nullptr);
+}
+
+TEST(StrTokTest, DelimitersShouldNotBeIncludedInToken) {
+  char src[] = "__ab__:_cd__:__ef__:__";
+  char *token = __llvm_libc::strtok(src, "_:");
+  ASSERT_STREQ(token, "ab");
+  token = __llvm_libc::strtok(nullptr, ":_");
+  ASSERT_STREQ(token, "cd");
+  token = __llvm_libc::strtok(nullptr, "_:,");
+  ASSERT_STREQ(token, "ef");
+  token = __llvm_libc::strtok(nullptr, "_:,_");
+  ASSERT_STREQ(token, nullptr);
+}