[libc] Add strtok_r implementation.

[sivachandra]

libc/spec/posix.td

17

Other restricted pointer types are named like RestrictSigSetType. For consistency, we should use just one style everywhere.

libc/src/string/strtok_r.cpp

17

Would it make sense to implement strtok and strtok_r over a common function which is equivalent in functionality to strtok_r?

36

Can we operator on src instead of saveptr?

if (*src) {
  *src = '\0';
  ++src;
}
*saveptr = src;

[cgyurgyik]

libc/spec/posix.td

17

Are you saying at the file level, or the libc level?
For example, in .../spec/stdc.td, it is named in the following manner:
RestrictedPtrType CharRestrictedPtr = RestrictedPtrType<CharType>. Which would we prefer?

[sivachandra]

libc/spec/posix.td

17

Keep it as in this patch then. We can cleanup separately.

[cgyurgyik]

libc/spec/posix.td

17

Ok I'll make a note for myself to fix this in a later revision. Currently seeing if there's a clean way to use a single function for both.

[abrachet]

libc/src/string/strtok_r.cpp

17

Making the prototype for this function restrict but not the function itself doesn't allow for optimizations. src and delimiter_string should be marked __restrict here and I imagine in a couple of other string functions too

[cgyurgyik]

libc/src/string/strtok_r.cpp

17

Yeah you're right, I haven't been using __restrict at all. I should've probably asked about this at an earlier point, wasn't sure if there was a reason to use it or not. Will fix this here, and other places in future revisions as well.

[cgyurgyik]

libc/src/string/strtok_r.cpp

17

I'm struggling to get a static inline function working for both a static char * and a char ** without running into lifetime issues with the saveptr. Was there something you had in mind? Maybe I'm missing something simple here.

[cgyurgyik]

libc/src/string/strtok_r.cpp

17

One way I could do this is to have the utility function return a struct {char *token, char *strtok_string}, and then set the strtok_string to the respective value, static char * for strtok, and dereferenced char** for strtok_r. Then we can return the struct.token.

[abrachet]

libc/src/string/strtok_r.cpp

17

strtok can just be

char *LLVM_LIBC_ENTRYPOINT(strtok)(char *src, const char *delimiter_string) {
  static char *strtok_str;
  return __llvm_libc::strtok_r(src, delimiter_string, &strtok_str);
}

There is no lifetime issue.

[cgyurgyik]

libc/src/string/strtok_r.cpp

17

Yep... that's the simple solution I avoided for much too long. I was trying to do the reverse. Will fix. Thanks abrachet :)

[cgyurgyik]

Address siva's and abrachet's comments.

[cgyurgyik]

libc/src/string/strtok_r.cpp

17

Left a TODO for myself to address this in a separate revision, since this applies to other functions as well.

[sivachandra]

LGTM but not yet accepting as I asked for some extension to the tests.

libc/src/string/string_utils.h

40

static?

libc/src/string/strtok_r.cpp

17

SGTM. And sorry I missed these in previous patches.

libc/test/src/string/strtok_r_test.cpp

12

While having these differently named tests is fine, I am mildly concerned with the fact that when I first read them, the tests seems incomplete. For example, most tests are making only a single call to strtok_r. The results of subsequent calls to strtok_r are not tested. I suggest putting all of this in one test called Various with each of the tests you have in their own comment annotated scoped block. For example:

Test(StrTokRTest, Various) {
  { // Empty source string and delimiter string
    char empty[] = "";
    char *reserve = nullptr;
    ASSERT_STREQ(__llvm_libc::strtok_r(empty, "",  &reserve), nullptr);
    // Another call to ensure that a bad state was not written in to |reserve|.
    ASSERT_STREQ(__llvm_libc::strtok_r(empty, "",  &reserve), nullptr);
    ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, "",  &reserve), nullptr);
  }
  ...
}

That said, putting everything in one test is my personal preference. You can choose to the keep the different test classes as you have currently, but include follow up calls to strtok_r as suggested in the above example.

[cgyurgyik]

Address siva's comments.

[cgyurgyik]

libc/src/string/string_utils.h

40

Thanks :). This was me trying to debug some quirky lifetime issues with the not-so-elegant approach I was taking beforehand.

libc/test/src/string/strtok_r_test.cpp

12

Thanks. Done. I'm still personally a fan of trying to separate behaviors by test, but I tried to group some of the bigger entities here.

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     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
+    libc.src.string.strtok_r
 )
 
 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/api.td

let Functions = [
     "strncmp",
     "strncpy",
     "strnlen",
     "strpbrk",
     "strrchr",
     "strspn",
     "strstr",
     "strtok",
+    "strtok_r",
     "strxfrm",   
   ];
 
   let TypeDeclarations = [
     SizeT,
   ];
 
   let Macros = [

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     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
+    libc.src.string.strtok_r
 
     # 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/spec/posix.td

 def SigSetType : NamedType<"sigset_t">;
 def SigSetPtrType : PtrType<SigSetType>;
 def ConstSigSetPtrType : ConstType<SigSetPtrType>;
 def RestrictSigSetType : RestrictedPtrType<SigSetType>;
 def ConstRestrictSigSetType : ConstType<RestrictSigSetType>;
 
 def StructSigaction : NamedType<"struct sigaction">;
 def StructSigactionPtr : PtrType<StructSigaction>;
 def ConstStructSigactionPtr : ConstType<StructSigactionPtr>;
 def RestrictStructSigactionPtr : RestrictedPtrType<StructSigaction>;
 def ConstRestrictStructSigactionPtr : ConstType<RestrictStructSigactionPtr>;
 
 def POSIX : StandardSpec<"POSIX"> {
+  // TODO: Change naming so that they're consistent with other files.
   PtrType CharPtr = PtrType<CharType>;
   ConstType ConstCharPtr = ConstType<CharPtr>;
+  RestrictedPtrType RestrictedCharPtr = RestrictedPtrType<CharType>;
+  ConstType ConstRestrictedCharPtr = ConstType<RestrictedCharPtr>;
+  RestrictedPtrType CharRestrictedDoublePtr = RestrictedPtrType<CharPtr>;
   NamedType OffTType = NamedType<"off_t">;
   NamedType SSizeTType = NamedType<"ssize_t">;
 
   HeaderSpec Errno = HeaderSpec<
       "errno.h",
       [
         Macro<"E2BIG">,
         Macro<"EACCES">,
HeaderSpec String = HeaderSpec<
     ],
     [], // Enumerations
     [
         FunctionSpec<
             "strnlen",
              RetValSpec<SizeTType>,
              [ArgSpec<ConstCharPtr>, ArgSpec<SizeTType>]
         >,
+        FunctionSpec<
+            "strtok_r",
+            RetValSpec<CharPtr>,
+            [ArgSpec<ConstRestrictedCharPtr>, ArgSpec<CharRestrictedDoublePtr>]
+        >,
     ]
   >;
 
   let Headers = [
     Errno,
     SysMMan,
     Signal,
     UniStd,
     String
   ];
 }

libc/src/string/CMakeLists.txt

 
 add_entrypoint_object(
   strtok
   SRCS
     strtok.cpp
   HDRS
     strtok.h
   DEPENDS
-    libc.utils.CPP.standalone_cpp
+    .string_utils
+)
+
+add_entrypoint_object(
+  strtok_r
+  SRCS
+    strtok_r.cpp
+  HDRS
+    strtok_r.h
+  DEPENDS
+    .string_utils
 )
 
 # 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)

libc/src/string/string_utils.h

static inline size_t complementary_span(const char *src, const char *segment) {
 
   for (; *segment; ++segment)
     bitset.set(*segment);
   for (; *src && !bitset.test(*src); ++src)
     ;
   return src - initial;
 }
 
+// Given the similarities between strtok and strtok_r, we can implement both
+// using a utility function. On the first call, 'src' is scanned for the
+// first character not found in 'delimiter_string'. Once found, it scans until
+// the first character in the 'delimiter_string' or the null terminator is
+// found. We define this span as a token. The end of the token is appended with
+// a null terminator, and the token is returned. The point where the last token
+// is found is then stored within 'context' for subsequent calls. Subsequent
+// calls will use 'context' when a nullptr is passed in for 'src'. Once the null
+// terminating character is reached, returns a nullptr.
+static inline char *string_token(char *src, const char *delimiter_string,
+                                 char **saveptr) {
+  cpp::Bitset<256> delimiter_set;
+  for (; *delimiter_string; ++delimiter_string)
+    delimiter_set.set(*delimiter_string);
+
+  src = src ? src : *saveptr;
+  for (; *src && delimiter_set.test(*src); ++src)
+    ;
+  if (!*src) {
+    *saveptr = src;
+    return nullptr;
+  }
+  char *token = src;
+  for (; *src && !delimiter_set.test(*src); ++src)
+    ;
+  if (*src) {
+    *src = '\0';
+    ++src;
+  }
+  *saveptr = src;
+  return token;
+}
+
 } // namespace internal
 } // namespace __llvm_libc
 
 #endif //  LIBC_SRC_STRING_STRING_UTILS_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"
+#include "src/string/string_utils.h"
 
 namespace __llvm_libc {
 
 static char *strtok_str = nullptr;
 
+// TODO: Place restrict qualifier where necessary for this and other function
+// arguments.
 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;
+  return internal::string_token(src, delimiter_string, &strtok_str);
 }
 
 } // namespace __llvm_libc

libc/src/string/strtok_r.h

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

libc/src/string/strtok_r.cpp

+//===-- Implementation of strtok_r ----------------------------------------===//
+//
+// 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_r.h"
+
+#include "src/__support/common.h"
+#include "src/string/string_utils.h"
+
+namespace __llvm_libc {
+
+char *LLVM_LIBC_ENTRYPOINT(strtok_r)(char *src, const char *delimiter_string,
+                                     char **saveptr) {
+  return internal::string_token(src, delimiter_string, saveptr);
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

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

+//===-- Unittests for strtok_r -------------------------------------------===//
+//
+// 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_r.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(StrTokReentrantTest, NoTokenFound) {
+  { // Empty source and delimiter string.
+    char empty[] = "";
+    char *reserve = nullptr;
+    ASSERT_STREQ(__llvm_libc::strtok_r(empty, "", &reserve), nullptr);
+    // Another call to ensure that 'reserve' is not in a bad state.
+    ASSERT_STREQ(__llvm_libc::strtok_r(empty, "", &reserve), nullptr);
+    ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, "", &reserve), nullptr);
+  }
+  { // Empty source and single character delimiter string.
+    char empty[] = "";
+    char *reserve = nullptr;
+    ASSERT_STREQ(__llvm_libc::strtok_r(empty, "_", &reserve), nullptr);
+    // Another call to ensure that 'reserve' is not in a bad state.
+    ASSERT_STREQ(__llvm_libc::strtok_r(empty, "_", &reserve), nullptr);
+    ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, "_", &reserve), nullptr);
+  }
+  { // Same character source and delimiter string.
+    char single[] = "_";
+    char *reserve = nullptr;
+    ASSERT_STREQ(__llvm_libc::strtok_r(single, "_", &reserve), nullptr);
+    // Another call to ensure that 'reserve' is not in a bad state.
+    ASSERT_STREQ(__llvm_libc::strtok_r(single, "_", &reserve), nullptr);
+    ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, "_", &reserve), nullptr);
+  }
+  { // Multiple character source and single character delimiter string.
+    char multiple[] = "1,2";
+    char *reserve = nullptr;
+    ASSERT_STREQ(__llvm_libc::strtok_r(multiple, ":", &reserve), "1,2");
+    // Another call to ensure that 'reserve' is not in a bad state.
+    ASSERT_STREQ(__llvm_libc::strtok_r(multiple, ":", &reserve), "1,2");
+    ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, ":", &reserve), nullptr);
+  }
+}
+
+TEST(StrTokReentrantTest, DelimiterAsFirstCharacterShouldBeIgnored) {
+  char src[] = ".123";
+  char *reserve = nullptr;
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ".", &reserve), "123");
+  // Another call to ensure that 'reserve' is not in a bad state.
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ".", &reserve), "123");
+  ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, ".", &reserve), nullptr);
+}
+
+TEST(StrTokReentrantTest, DelimiterIsMiddleCharacter) {
+  char src[] = "12,34";
+  char *reserve = nullptr;
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ",", &reserve), "12");
+  // Another call to ensure that 'reserve' is not in a bad state.
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ",", &reserve), "12");
+  ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, ",", &reserve), nullptr);
+}
+
+TEST(StrTokReentrantTest, DelimiterAsLastCharacterShouldBeIgnored) {
+  char src[] = "1234:";
+  char *reserve = nullptr;
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ":", &reserve), "1234");
+  // Another call to ensure that 'reserve' is not in a bad state.
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ":", &reserve), "1234");
+  ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, ":", &reserve), nullptr);
+}
+
+TEST(StrTokReentrantTest, ShouldNotGoPastNullTerminator) {
+  char src[] = {'1', '2', '\0', ',', '3'};
+  char *reserve = nullptr;
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ",", &reserve), "12");
+  // Another call to ensure that 'reserve' is not in a bad state.
+  ASSERT_STREQ(__llvm_libc::strtok_r(src, ",", &reserve), "12");
+  ASSERT_STREQ(__llvm_libc::strtok_r(nullptr, ",", &reserve), nullptr);
+}
+
+TEST(StrTokReentrantTest, SubsequentCallsShouldFindFollowingDelimiters) {
+  char src[] = "12,34.56";
+  char *reserve = nullptr;
+  char *token = __llvm_libc::strtok_r(src, ",.", &reserve);
+  ASSERT_STREQ(token, "12");
+  token = __llvm_libc::strtok_r(nullptr, ",.", &reserve);
+  ASSERT_STREQ(token, "34");
+  token = __llvm_libc::strtok_r(nullptr, ",.", &reserve);
+  ASSERT_STREQ(token, "56");
+  token = __llvm_libc::strtok_r(nullptr, "_:,_", &reserve);
+  ASSERT_STREQ(token, nullptr);
+  // Subsequent calls after hitting the end of the string should also return
+  // nullptr.
+  token = __llvm_libc::strtok_r(nullptr, "_:,_", &reserve);
+  ASSERT_STREQ(token, nullptr);
+}
+
+TEST(StrTokReentrantTest, DelimitersShouldNotBeIncludedInToken) {
+  char src[] = "__ab__:_cd__:__ef__:__";
+  char *reserve = nullptr;
+  char *token = __llvm_libc::strtok_r(src, "_:", &reserve);
+  ASSERT_STREQ(token, "ab");
+  token = __llvm_libc::strtok_r(nullptr, ":_", &reserve);
+  ASSERT_STREQ(token, "cd");
+  token = __llvm_libc::strtok_r(nullptr, "_:,", &reserve);
+  ASSERT_STREQ(token, "ef");
+  token = __llvm_libc::strtok_r(nullptr, "_:,_", &reserve);
+  ASSERT_STREQ(token, nullptr);
+}