[libc] Add strspn implementation.

[cgyurgyik]

Summary

[libc] Adds strspn implementation and Bitset to CPP utils. To get O(max(M,N)) complexity (where M, N are the string lengths), one can use a table to first store the characters of the string to be matched against, and then iterate over the source string to determine if it contains any.

This approach takes it a step further, and reduces the table's size by using bit manipulation techniques.

[cgyurgyik]

This is a working draft; currently not sure what the best approach for this is. I just stuck a few helper functions in that have some duplication, as well as some constants. I'm assuming this won't be the only function to use bit manipulation; maybe there already exists one for libc that I'm just not aware of.

Thanks ahead of time for the guidance and reviews.

[abrachet]

FWIW, I think in most real world scenarios the O(N*M) approach would be faster. Granted I don't know what those scenarios are I had never heard of this function, I have no idea where this is useful.

libc/src/string/strspn.cpp

17

None of the comments in this file are necessary I would say. This code explains itself.

18

static not necessary. Also I think that the naming convention is wrong here, it should be the same as all other identifiers.

20–21

The size of the byteset used. Not necessary.
The rest if you think that is actually a concern, presumably not then we should static_assert it otherwise remove that comment too.

22

32 is supposed to be how many bytes it takes to represent 256 bits? Maybe (256 / 8) / sizeof(size_t) is easier to read? This might have actually warranted a comment

Also should this be called a bitset not a byteset?

25

inline not necessary. Instead of taking an unsigned char then assigning it to a size_t just take a size_t here and in contains_bit.

32

byteset should be a const size_t *

43–52

The difference in speed here is going to be negligible, the question is wether you think it is worth complicating the code for these edge cases.

[cgyurgyik]

In D85103#2192569, @abrachet wrote:

FWIW, I think in most real world scenarios the O(N*M) approach would be faster. Granted I don't know what those scenarios are I had never heard of this function, I have no idea where this is useful.

Its hard for me to argue this claim one way or another without an appropriate data set to benchmark with. Therefore, I chose to rely solely on complexity for now.

[cgyurgyik]

Address abrachet's comments.

libc/src/string/strspn.cpp

18

Yeah I couldn't find much on constants naming convention. Changed to lowercase.

20–21

I don't know any systems that have a size_t > 32 bytes. I'll remove this for now.

25

Is there any harm in inline here? I removed it, but for my own knowledge. From what I understand, you're saying the compiler will inline it on its own accord, and this is just extra unnecessary specifier?

32

Good catch thanks.

43–52

This is something Siva hit me on before as well, so I'll wait for his input here too. I understand your thinking, but I don't find it grossly complicated, and think its good to avoid creating a bitset unless absolutely necessary.

[cgyurgyik]

libc/src/string/strspn.cpp

22

I think arguments could be made for both, but I like bitset a bit more.

[cgyurgyik]

libc/src/string/strspn.cpp

33–41

I believe I accidentally resolved this, but
@abrachet 's comment from earlier:

The difference in speed here is going to be negligible, the question is whether you think it is worth complicating the code for these edge cases.

[sivachandra]

libc/src/string/strspn.cpp

22

I would prefer a bool specialization of https://github.com/llvm/llvm-project/blob/master/libc/utils/CPP/Array.h for which the internal implementation is a bit array like std::vector<bool>.

Also, why not use uintptr_t array instead of size_t array?

static constexpr size_t BitsPerUnit = 8 * sizeof(uintptr_t);
uintptr_t Data[size / BitsPerUnit + size % BitsPerUnit]; // size is of type size_t

// Setter; x is of type size_t
Data[x / BitsPerUnit] |= (uintptr_t(1) << (x % BitsPerUnit));

// Getter; x is of type size_t
return Data[x / BitsPerUnit] & (uintptr_t(1) << (x % BitsPerUnit));

33–41

I agree with @abrachet that this has almost no benefit.

[cgyurgyik]

Address some of Siva's comments, still need to use array<bool> representation.

[cgyurgyik]

libc/src/string/strspn.cpp

22

Ok I'll work on this.

[cgyurgyik]

libc/src/string/strspn.cpp

22

Discussed offline - going to add std::bitset util instead, since std::array<bool, size_t> doesn't mimic the std::vector<bool> implementation.

[cgyurgyik]

Adds Bitset to CPP utils.

[sivachandra]

libc/test/src/string/strspn_test.cpp

14

Seems to me like all of these tests should just be combined into one test as the different names are making it more confusing.

libc/test/utils/CPP/bitset_test.cpp

2

Uppercase *B*itset.

58

Seems like SetsProperBit and DoesNotSetNeighbotBts should be combined into something like SettingXDoesNotSetY.

80

May be EXPECT_TRUE(...).

86

s/Should/Does ?

libc/utils/CPP/Bitset.h

19

s/CharacterBit/BitsPerByte ?

23

If number_of_bits is always > zero, will the calculated size be zero?

44

Because there is a static assert to ensure NumberOfBits is not 0, why not just do:

uintptr_t Data[(NumberOfBits + BitsPerByte - 1)/BitsPerUnit] = {0};

[cgyurgyik]

Address Siva's comments.

[cgyurgyik]

libc/test/src/string/strspn_test.cpp

14

Can you clarify what you mean here?
I'm trying to unit test strspn, i.e. test different behaviors so that if it fails for behavior X, then behavior X unit test should fail rather than all of them. This has helped me already with some small debugging problems when manipulating bits.

I agree that my naming isn't phenomenal, but its hard when trying to talk about spans and segments. I an open to naming changes and combining certain tests, but I don't know if combining all the unit tests is the correct approach.

With that said, I've made some changes to the names in hopes to improve this.

libc/utils/CPP/Bitset.h

44

Let

NumberOfBits = 16
BitsPerByte = 8
BitsPerUnit = BitsPerByte * sizeof(uintptr_t) = 8 * 4

(NumberOfBits + BitsPerByte - 1) / BitsPerUnit
= (16 + 8 - 1) / (8 * 4)
= 23 / 32
= 0

If (NumberOfBits + BitsPerByte - 1) < BitsPerUnit, then we get 0.
I can simplify this further and just say if NumberOfBits < BitsPerUnit, return 1 unit.

[sivachandra]

libc/utils/CPP/Bitset.h

19

Make these static members of Bitset.

37

Sorry, I had a typo in my earlier comment. It should have been:

(NumberOfBits + BitsPerUnit - 1)/BitsPerUnit

This should handle all cases?

[cgyurgyik]

libc/utils/CPP/Bitset.h

37

Yep! Good call on this. That should've been the obvious next step.

[cgyurgyik]

Thanks for the review Siva. Will wait for @abrachet 's LGTM as well.

[abrachet]

Missing definition in spec/stdc.td

[cgyurgyik]

In D85103#2197398, @abrachet wrote:

Missing definition in spec/stdc.td

https://github.com/llvm/llvm-project/blob/1dbac09dd6ec8587ae7e16ed669bf73889a21957/libc/spec/stdc.td#L214 ?

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.memset
     libc.src.string.memrchr
     libc.src.string.strcat
     libc.src.string.strchr
     libc.src.string.strcpy
     libc.src.string.strlen
     libc.src.string.strnlen
     libc.src.string.strrchr
+    libc.src.string.strspn
     libc.src.string.strstr
 )
 
 set(TARGET_LIBM_ENTRYPOINTS
     # math.h entrypoints
     libc.src.math.copysign
     libc.src.math.copysignf
     libc.src.math.copysignl

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.memset
     libc.src.string.strcat
     libc.src.string.strchr
     libc.src.string.strcmp
     libc.src.string.strcpy
     libc.src.string.strlen
     libc.src.string.strnlen
     libc.src.string.strrchr
+    libc.src.string.strspn
     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/string/CMakeLists.txt

 add_entrypoint_object(
   strrchr
   SRCS
     strrchr.cpp
   HDRS
     strrchr.h
 )
 
+add_entrypoint_object(
+  strspn
+  SRCS
+    strspn.cpp
+  HDRS
+    strspn.h
+)
+
 # 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/strspn.h

+//===-- Implementation header for strspn ------------------------*- 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_STRSPN_H
+#define LLVM_LIBC_SRC_STRING_STRSPN_H
+
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+size_t strspn(const char *src, const char *segment);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_STRSPN_H

libc/src/string/strspn.cpp

+//===-- Implementation of strspn ------------------------------------------===//
+//
+// 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/strspn.h"
+
+#include "src/__support/common.h"
+#include "utils/CPP/Bitset.h"
+#include <stddef.h>
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+size_t LLVM_LIBC_ENTRYPOINT(strspn)(const char *src, const char *segment) {
+  const char *initial = src;
+  cpp::Bitset<256> bitset;
+
+  for (; *segment; ++segment)
+    bitset.set(*segment);
+  for (; *src && bitset.test(*src); ++src)
+    ;
+  return src - initial;
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_string_unittests
   SRCS
     strrchr_test.cpp
   DEPENDS
     libc.src.string.strrchr
 )
 
+add_libc_unittest(
+  strspn_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    strspn_test.cpp
+  DEPENDS
+    libc.src.string.strspn
+)
+
+
 # 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/strspn_test.cpp

+//===-- Unittests for strspn ----------------------------------------------===//
+//
+// 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/strspn.h"
+
+#include "utils/UnitTest/Test.h"
+
+TEST(StrSpnTest, EmptyStringShouldReturnZeroLengthSpan) {
+  // The search should not include the null terminator.
+  EXPECT_EQ(__llvm_libc::strspn("", ""), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn("_", ""), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn("", "_"), size_t{0});
+}
+
+TEST(StrSpnTest, ShouldNotSpanAnythingAfterNullTerminator) {
+  const char src[4] = {'a', 'b', '\0', 'c'};
+  EXPECT_EQ(__llvm_libc::strspn(src, "ab"), size_t{2});
+  EXPECT_EQ(__llvm_libc::strspn(src, "c"), size_t{0});
+
+  // Same goes for the segment to be searched for.
+  const char segment[4] = {'1', '2', '\0', '3'};
+  EXPECT_EQ(__llvm_libc::strspn("123", segment), size_t{2});
+}
+
+TEST(StrSpnTest, SpanEachIndividualCharacter) {
+  const char *src = "12345";
+  EXPECT_EQ(__llvm_libc::strspn(src, "1"), size_t{1});
+  // Since '1' is not within the segment, the span
+  // size should remain zero.
+  EXPECT_EQ(__llvm_libc::strspn(src, "2"), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn(src, "3"), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn(src, "4"), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn(src, "5"), size_t{0});
+}
+
+TEST(StrSpnTest, UnmatchedCharacterShouldNotBeCountedInSpan) {
+  EXPECT_EQ(__llvm_libc::strspn("a", "b"), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn("abcdef", "1"), size_t{0});
+  EXPECT_EQ(__llvm_libc::strspn("123", "4"), size_t{0});
+}
+
+TEST(StrSpnTest, SequentialCharactersShouldSpan) {
+  const char *src = "abcde";
+  EXPECT_EQ(__llvm_libc::strspn(src, "a"), size_t{1});
+  EXPECT_EQ(__llvm_libc::strspn(src, "ab"), size_t{2});
+  EXPECT_EQ(__llvm_libc::strspn(src, "abc"), size_t{3});
+  EXPECT_EQ(__llvm_libc::strspn(src, "abcd"), size_t{4});
+  EXPECT_EQ(__llvm_libc::strspn(src, "abcde"), size_t{5});
+  // Same thing for when the roles are reversed.
+  EXPECT_EQ(__llvm_libc::strspn("abcde", src), size_t{5});
+  EXPECT_EQ(__llvm_libc::strspn("abcd", src), size_t{4});
+  EXPECT_EQ(__llvm_libc::strspn("abc", src), size_t{3});
+  EXPECT_EQ(__llvm_libc::strspn("ab", src), size_t{2});
+  EXPECT_EQ(__llvm_libc::strspn("a", src), size_t{1});
+}
+
+TEST(StrSpnTest, NonSequentialCharactersShouldNotSpan) {
+  const char *src = "123456789";
+  EXPECT_EQ(__llvm_libc::strspn(src, "_1_abc_2_def_3_"), size_t{3});
+  // Only spans 4 since '5' is not within the span.
+  EXPECT_EQ(__llvm_libc::strspn(src, "67__34abc12"), size_t{4});
+}
+
+TEST(StrSpnTest, ReverseCharacters) {
+  // Since these are still sequential, this should span.
+  EXPECT_EQ(__llvm_libc::strspn("12345", "54321"), size_t{5});
+  // Does not span any since '1' is not within the span.
+  EXPECT_EQ(__llvm_libc::strspn("12345", "432"), size_t{0});
+  // Only spans 1 since '2' is not within the span.
+  EXPECT_EQ(__llvm_libc::strspn("12345", "51"), size_t{1});
+}
+
+TEST(StrSpnTest, DuplicatedCharactersToBeSearchedForShouldStillMatch) {
+  // Only a single character, so only spans 1.
+  EXPECT_EQ(__llvm_libc::strspn("a", "aa"), size_t{1});
+  // This should count once for each 'a' in the source string.
+  EXPECT_EQ(__llvm_libc::strspn("aa", "aa"), size_t{2});
+  EXPECT_EQ(__llvm_libc::strspn("aaa", "aa"), size_t{3});
+  EXPECT_EQ(__llvm_libc::strspn("aaaa", "aa"), size_t{4});
+}

libc/test/utils/CMakeLists.txt

 add_subdirectory(FPUtil)
+add_subdirectory(CPP)

libc/test/utils/CPP/CMakeLists.txt

+add_libc_testsuite(libc_cpp_utils_unittests)
+
+add_libc_unittest(
+  bitset_test
+  SUITE
+    libc_cpp_utils_unittests
+  SRCS
+    bitset_test.cpp
+  DEPENDS
+    libc.utils.CPP.standalone_cpp
+)

libc/test/utils/CPP/bitset_test.cpp

+//===-- Unittests for Bitset ----------------------------------------------===//
+//
+// 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 "utils/CPP/Bitset.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(BitsetTest, SetBitForSizeEqualToOne) {
+  __llvm_libc::cpp::Bitset<1> bitset;
+  EXPECT_FALSE(bitset.test(0));
+  bitset.set(0);
+  EXPECT_TRUE(bitset.test(0));
+}
+
+TEST(BitsetTest, SetsBitsForSizeEqualToTwo) {
+  __llvm_libc::cpp::Bitset<2> bitset;
+  bitset.set(0);
+  EXPECT_TRUE(bitset.test(0));
+  bitset.set(1);
+  EXPECT_TRUE(bitset.test(1));
+}
+
+TEST(BitsetTest, SetsAllBitsForSizeLessThanEight) {
+  __llvm_libc::cpp::Bitset<7> bitset;
+  for (size_t i = 0; i < 7; ++i)
+    bitset.set(i);
+  // Verify all bits are now set.
+  for (size_t j = 0; j < 7; ++j)
+    EXPECT_TRUE(bitset.test(j));
+}
+
+TEST(BitsetTest, SetsAllBitsForSizeLessThanSixteen) {
+  __llvm_libc::cpp::Bitset<15> bitset;
+  for (size_t i = 0; i < 15; ++i)
+    bitset.set(i);
+  // Verify all bits are now set.
+  for (size_t j = 0; j < 15; ++j)
+    EXPECT_TRUE(bitset.test(j));
+}
+
+TEST(BitsetTest, SetsAllBitsForSizeLessThanThirtyTwo) {
+  __llvm_libc::cpp::Bitset<31> bitset;
+  for (size_t i = 0; i < 31; ++i)
+    bitset.set(i);
+  // Verify all bits are now set.
+  for (size_t j = 0; j < 31; ++j)
+    EXPECT_TRUE(bitset.test(j));
+}
+
+TEST(BitsetTest, DefaultHasNoSetBits) {
+  __llvm_libc::cpp::Bitset<64> bitset;
+  for (size_t i = 0; i < 64; ++i) {
+    EXPECT_FALSE(bitset.test(i));
+  }
+  // Same for odd number.
+  __llvm_libc::cpp::Bitset<65> odd_bitset;
+  for (size_t i = 0; i < 65; ++i) {
+    EXPECT_FALSE(odd_bitset.test(i));
+  }
+}
+
+TEST(BitsetTest, SettingBitXDoesNotSetBitY) {
+  for (size_t i = 0; i < 256; ++i) {
+    // Initialize within the loop to start with a fresh Bitset.
+    __llvm_libc::cpp::Bitset<256> bitset;
+    bitset.set(i);
+
+    for (size_t neighbor = 0; neighbor < 256; ++neighbor) {
+      if (neighbor == i)
+        EXPECT_TRUE(bitset.test(neighbor));
+      else
+        EXPECT_FALSE(bitset.test(neighbor));
+    }
+  }
+  // Same for odd number.
+  for (size_t i = 0; i < 255; ++i) {
+
+    __llvm_libc::cpp::Bitset<255> bitset;
+    bitset.set(i);
+
+    for (size_t neighbor = 0; neighbor < 255; ++neighbor) {
+      if (neighbor == i)
+        EXPECT_TRUE(bitset.test(neighbor));
+      else
+        EXPECT_FALSE(bitset.test(neighbor));
+    }
+  }
+}
+
+TEST(BitsetTest, SettingBitXDoesNotResetBitY) {
+  __llvm_libc::cpp::Bitset<128> bitset;
+  for (size_t i = 0; i < 128; ++i)
+    bitset.set(i);
+
+  // Verify all bits are now set.
+  for (size_t j = 0; j < 128; ++j)
+    EXPECT_TRUE(bitset.test(j));
+}

libc/utils/CPP/Bitset.h

+//===-- A self contained equivalent of std::bitset --------------*- 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_UTILS_CPP_BITSET_H
+#define LLVM_LIBC_UTILS_CPP_BITSET_H
+
+#include <stddef.h> // For size_t.
+#include <stdint.h> // For uintptr_t.
+
+namespace __llvm_libc {
+namespace cpp {
+
+template <size_t NumberOfBits> struct Bitset {
+  static_assert(NumberOfBits != 0,
+                "Cannot create a __llvm_libc::cpp::Bitset of size 0.");
+
+  constexpr void set(size_t Index) {
+    Data[Index / BitsPerUnit] |= (uintptr_t{1} << (Index % BitsPerUnit));
+  }
+
+  constexpr bool test(size_t Index) const {
+    return Data[Index / BitsPerUnit] & (uintptr_t{1} << (Index % BitsPerUnit));
+  }
+
+private:
+  static constexpr size_t BitsPerByte = 8;
+  static constexpr size_t BitsPerUnit = BitsPerByte * sizeof(uintptr_t);
+  uintptr_t Data[(NumberOfBits + BitsPerUnit - 1) / BitsPerUnit] = {0};
+};
+
+} // namespace cpp
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_UTILS_CPP_BITSET_H

libc/utils/CPP/CMakeLists.txt

 add_header_library(
   standalone_cpp
   HDRS
     Array.h
     ArrayRef.h
+    Bitset.h
     Functional.h
     StringRef.h
     TypeTraits.h
 )