[libc] Implement strsep

[mcgrathr]

This is missing the bsd_ext.td addition for the <string.h> decl.

libc/test/src/string/strsep_test.cpp

2

Perhaps you can templatize the strtok test and then reuse that here.
Both functions should have all the same cases covered.

[michaelrj]

I'm not finding good documentation online, but according to the man page for strsep, it should behave slightly differently from strtok. Instead of skipping past repeated delimeters, it should instead treat them the same and possibly return a pointer to '\0'. I've copied the example below:

EXAMPLES
       The program below is a port of the one found in strtok(3), which, however, doesn't discard multiple delimiters
       or empty tokens:

           $ ./a.out 'a/bbb///cc;xxx:yyy:' ':;' '/'
           1: a/bbb///cc
                    --> a
                    --> bbb
                    -->
                    -->
                    --> cc
           2: xxx
                    --> xxx
           3: yyy
                    --> yyy
           4:
                    -->

   Program source

       #include <stdio.h>
       #include <stdlib.h>
       #include <string.h>

       int
       main(int argc, char *argv[])
       {
           char *token, *subtoken;

           if (argc != 4) {
               fprintf(stderr, "Usage: %s string delim subdelim\n", argv[0]);
               exit(EXIT_FAILURE);
           }

           for (unsigned int j = 1; (token = strsep(&argv[1], argv[2])); j++) {
               printf("%u: %s\n", j, token);

               while ((subtoken = strsep(&token, argv[3])))
                   printf("\t --> %s\n", subtoken);
           }

           exit(EXIT_SUCCESS);
       }

SEE ALSO
       index(3), memchr(3), rindex(3), strchr(3), string(3), strpbrk(3), strspn(3), strstr(3), strtok(3)

Linux man-pages 6.01                                  2022-10-09                                            STRSEP(3)

[abrachet]

Good catch, thanks.

[michaelrj]

LGTM with one nit.

libc/src/string/string_utils.h

197–199

Nit: This should be if constexpr (SkipDelim) to make it clear this is a compile-time if statement.

[abrachet]

libc/src/string/string_utils.h

197–199

Done in commit

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.strncasecmp
     libc.src.string.strncat
     libc.src.string.strncmp
     libc.src.string.strncpy
     libc.src.string.strndup
     libc.src.string.strnlen
     libc.src.string.strpbrk
     libc.src.string.strrchr
+    libc.src.string.strsep
     libc.src.string.strsignal
     libc.src.string.strspn
     libc.src.string.strstr
     libc.src.string.strtok
     libc.src.string.strtok_r
 
     # inttypes.h entrypoints
     libc.src.inttypes.imaxabs

libc/config/linux/arm/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.strlen
     libc.src.string.strncasecmp
     libc.src.string.strncat
     libc.src.string.strncmp
     libc.src.string.strncpy
     libc.src.string.strnlen
     libc.src.string.strpbrk
     libc.src.string.strrchr
+    libc.src.string.strsep
     libc.src.string.strspn
     libc.src.string.strstr
     libc.src.string.strtok
     libc.src.string.strtok_r
 
     # inttypes.h entrypoints
     libc.src.inttypes.imaxabs
     libc.src.inttypes.imaxdiv

libc/config/linux/riscv64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.strncasecmp
     libc.src.string.strncat
     libc.src.string.strncmp
     libc.src.string.strncpy
     libc.src.string.strndup
     libc.src.string.strnlen
     libc.src.string.strpbrk
     libc.src.string.strrchr
+    libc.src.string.strsep
     libc.src.string.strsignal
     libc.src.string.strspn
     libc.src.string.strstr
     libc.src.string.strtok
     libc.src.string.strtok_r
 
     # inttypes.h entrypoints
     libc.src.inttypes.imaxabs

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.strncasecmp
     libc.src.string.strncat
     libc.src.string.strncmp
     libc.src.string.strncpy
     libc.src.string.strndup
     libc.src.string.strnlen
     libc.src.string.strpbrk
     libc.src.string.strrchr
+    libc.src.string.strsep
     libc.src.string.strsignal
     libc.src.string.strspn
     libc.src.string.strstr
     libc.src.string.strtok
     libc.src.string.strtok_r
 
     # inttypes.h entrypoints
     libc.src.inttypes.imaxabs

libc/spec/bsd_ext.td

HeaderSpec String = HeaderSpec<
             RetValSpec<SizeTType>,
             [ArgSpec<CharPtr>, ArgSpec<ConstCharPtr>, ArgSpec<SizeTType>]
         >,
         FunctionSpec<
             "strlcpy",
             RetValSpec<SizeTType>,
             [ArgSpec<CharPtr>, ArgSpec<ConstCharPtr>, ArgSpec<SizeTType>]
         >,
+        FunctionSpec<
+            "strsep",
+            RetValSpec<CharPtr>,
+            [ArgSpec<CharRestrictedPtrPtr>, ArgSpec<ConstCharRestrictedPtr>]
+        >,
       ]
   >;
 
   HeaderSpec Strings = HeaderSpec<
       "strings.h",
       [], // Macros
       [], // Types
       [], // Enumerations

libc/src/string/CMakeLists.txt

add_entrypoint_object(
   strrchr
   SRCS
     strrchr.cpp
   HDRS
     strrchr.h
 )
 
 add_entrypoint_object(
+  strsep
+  SRCS
+    strsep.cpp
+  HDRS
+    strsep.h
+  DEPENDS
+    .string_utils
+)
+
+add_entrypoint_object(
   strsignal
   SRCS
     strsignal.cpp
   HDRS
     strsignal.h
   DEPENDS
     libc.src.__support.StringUtil.signal_to_string
 )

libc/src/string/string_utils.h

 // 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.
+template <bool SkipDelim = true>
 LIBC_INLINE char *string_token(char *__restrict src,
                                const char *__restrict delimiter_string,
                                char **__restrict saveptr) {
   // Return nullptr immediately if both src AND saveptr are nullptr
   if (LIBC_UNLIKELY(src == nullptr && ((src = *saveptr) == nullptr)))
     return nullptr;
 
   cpp::bitset<256> delimiter_set;
   for (; *delimiter_string != '\0'; ++delimiter_string)
     delimiter_set.set(*delimiter_string);
 
+  if constexpr (SkipDelim)
     for (; *src != '\0' && delimiter_set.test(*src); ++src)
       ;
   if (*src == '\0') {
     *saveptr = src;
     return nullptr;
   }
   char *token = src;
   for (; *src != '\0'; ++src) {
     if (delimiter_set.test(*src)) {
       *src = '\0';

libc/src/string/strsep.h

+//===-- Implementation header for strsep ------------------------*- 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_STRSEP_H
+#define LLVM_LIBC_SRC_STRING_STRSEP_H
+
+namespace __llvm_libc {
+
+char *strsep(char **stringp, const char *delim);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_STRSEP_H

libc/src/string/strsep.cpp

+//===-- Implementation of strsep ------------------------------------------===//
+//
+// 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/strsep.h"
+
+#include "src/string/string_utils.h"
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(char *, strsep, (char **stringp, const char *delim)) {
+  if (!*stringp)
+    return nullptr;
+  return internal::string_token<false>(*stringp, delim, stringp);
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

SUITE
     libc_string_unittests
   SRCS
     strrchr_test.cpp
   DEPENDS
     libc.src.string.strrchr
 )
 
 add_libc_unittest(
+  strsep_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    strsep_test.cpp
+  DEPENDS
+    libc.src.string.strsep
+)
+
+add_libc_unittest(
   strsignal_test
   SUITE
     libc_string_unittests
   SRCS
     strsignal_test.cpp
   DEPENDS
     libc.src.string.strsignal
 )

libc/test/src/string/strsep_test.cpp

+//===-- Unittests for strsep ----------------------------------------------===//
+//
+// 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/strsep.h"
+#include "test/UnitTest/Test.h"
+
+TEST(LlvmLibcStrsepTest, NullSrc) {
+  char *string = nullptr;
+  EXPECT_STREQ(__llvm_libc::strsep(&string, ""), nullptr);
+}
+
+TEST(LlvmLibcStrsepTest, NoTokenFound) {
+  {
+    char s[] = "";
+    char *string = s, *orig = s;
+    EXPECT_STREQ(__llvm_libc::strsep(&string, ""), nullptr);
+    EXPECT_EQ(orig, string);
+  }
+  {
+    char s[] = "abcde";
+    char *string = s, *orig = s;
+    EXPECT_STREQ(__llvm_libc::strsep(&string, ""), orig);
+    EXPECT_EQ(string, orig + 5);
+  }
+  {
+    char s[] = "abcde";
+    char *string = s, *orig = s;
+    EXPECT_STREQ(__llvm_libc::strsep(&string, "fghijk"), orig);
+    EXPECT_EQ(string, orig + 5);
+  }
+}
+
+TEST(LlvmLibcStrsepTest, TokenFound) {
+  char s[] = "abacd";
+  char *string = s;
+  EXPECT_STREQ(__llvm_libc::strsep(&string, "c"), "aba");
+  EXPECT_STREQ(string, "d");
+}
+
+TEST(LlvmLibcStrsepTest, DelimitersShouldNotBeIncludedInToken) {
+  char s[] = "__ab__:cd_:_ef_:_";
+  char *string = s;
+  const char *expected[] = {"", "",   "ab", "", "", "cd",   "",
+                            "", "ef", "",   "", "", nullptr};
+  for (int i = 0; expected[i]; i++) {
+    ASSERT_STREQ(__llvm_libc::strsep(&string, "_:"), expected[i]);
+  }
+}