[libc] Adds strrchr implementation.

[cgyurgyik]

Summary

Rationale: A naive approach may first use strlen to find the string length, then memrchr to match. This is similar, but just does both in the same loop. Since '\0' is a valid character to match with, we need to ensure that it is checked after the comparison.

[sivachandra]

libc/src/string/strrchr.cpp

25

Nit: To avoid the post-increment operator, may be:

for (; ; ++str) {
  if (*str == ch)
    last_occurance = str;
  if (*str == '\0')
    break;
}

To me personally, mixing post/pre-increment operators with other operators make it hard to read so this comment is also driven by my personal preference.

[sivachandra]

libc/test/src/string/strrchr_test.cpp

12

Nit: For completeness, may be add a test where src points to a byte string having more than one null terminators.

[cgyurgyik]

Thanks for the review Siva.

libc/src/string/strrchr.cpp

25

I battled with this for a bit as well, but found using a do...while loop cleaner. For this reason, I'm going to leave it as is.

[abrachet]

Clearly I'm too late but there are some problems with this revision.

libc/src/string/strrchr.cpp

16–17

Do the const cast at the end. Siva is right too *str++ is an operator precedence rule away from modifying src which is particularly scary when you've const casted early.

18

const not useful here. In any case you can just do c = static_cast<unsigned char>(c). Also why unsigned? Whats wrong with keeping str as a const char *?

25

+1 to Siva's suggestion. The break can be return last_occurance;

libc/test/src/string/strrchr_test.cpp

18–19

This doesn't do anything. You want ASSERT_STREQ(src, "abcde"); And for the next 3 tests. Also all 4 of these can be consolidated into the same function.

[sivachandra]

libc/test/src/string/strrchr_test.cpp

18–19

Ah, good catch! I missed it in the strchr_test as well.

[cgyurgyik]

libc/test/src/string/strrchr_test.cpp

18–19

Yep thanks will fix.

[cgyurgyik]

libc/src/string/strrchr.cpp

16–17

*str++ occurs in the order one might expect if they read it left to right, and follows C operator precedence as expected in this implementation. However, I am not tied to this, and understand your concerns. I will change it in a follow-up revision.

18

Can you explain what you mean by const not useful here?

Is there a difference between what I have and c = static_cast<unsigned char>(c)?

As for your third question, I chose to reinterpret it after reading "each character interpreted as unsigned char": https://en.cppreference.com/w/c/string/byte/strchr

[cgyurgyik]

libc/test/src/string/strrchr_test.cpp

18–19

Are you saying consolidate the "source string should not change" part?

[abrachet]

libc/src/string/strrchr.cpp

16–17

I'm not questioning the order of precedence, I'm saying for data that we are not allowed to change we should rely on const. I am tied to doing the const_cast at the end. const_cast is dangerous and we should only do it when we absolutely need to.

18

const is useful as a contract for shared state. There isn't a compelling reason to make private state const in my opinion.

Not after optimizations presumably.

FWIW the C standard says "The strrchr function locates the last occurrence of c (converted to a char) in the string pointed to by s" Regardless signedness won't change equality so this is just an extra step we don't need to take as it's just adding unnecessary code.

[cgyurgyik]

libc/src/string/strrchr.cpp

16–17

Agreed, const_cast later is the safer option. I did the cast early to avoid having to call it in the while loop.

18

To me, const simply means I don't want the value associated with it to change. In this case, I don't want ch to change later in the function call. This is another layer of type safety.

FWIW the C standard says "The strrchr function locates the last occurrence of c (converted to a char) in the string pointed to by s"

Noted, I'll avoid the unsigned char conversion here.

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.string.memcpy
     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.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.memrchr
     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.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(
   memrchr
   SRCS
     memrchr.cpp
   HDRS
     memrchr.h
 )
 
+add_entrypoint_object(
+  strrchr
+  SRCS
+    strrchr.cpp
+  HDRS
+    strrchr.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/strrchr.h

+//===-- Implementation header for strrchr -----------------------*- 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_STRRCHR_H
+#define LLVM_LIBC_SRC_STRING_STRRCHR_H
+
+namespace __llvm_libc {
+
+char *strrchr(const char *src, int c);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_STRRCHR_H

libc/src/string/strrchr.cpp

+//===-- Implementation of strrchr------------------------------------------===//
+//
+// 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/strrchr.h"
+
+#include "src/__support/common.h"
+
+namespace __llvm_libc {
+
+char *LLVM_LIBC_ENTRYPOINT(strrchr)(const char *src, int c) {
+  unsigned char *str =
+      const_cast<unsigned char *>(reinterpret_cast<const unsigned char *>(src));
+  const unsigned char ch = c;
+
+  unsigned char *last_occurrence = nullptr;
+  do {
+    if (*str == ch)
+      last_occurrence = str;
+  } while (*str++);
+  return reinterpret_cast<char *>(last_occurrence);
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

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

+//===-- Unittests for strrchr ---------------------------------------------===//
+//
+// 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/strrchr.h"
+#include "utils/UnitTest/Test.h"
+
+TEST(StrRChrTest, FindsFirstCharacter) {
+  const char *src = "abcde";
+  const char *src_copy = src;
+
+  // Should return original string since 'a' is the first character.
+  ASSERT_STREQ(__llvm_libc::strrchr(src, 'a'), "abcde");
+  // Source string should not change.
+  ASSERT_STREQ(src, src_copy);
+}
+
+TEST(StrRChrTest, FindsMiddleCharacter) {
+  const char *src = "abcde";
+  const char *src_copy = src;
+
+  // Should return characters after (and including) 'c'.
+  ASSERT_STREQ(__llvm_libc::strrchr(src, 'c'), "cde");
+  // Source string should not change.
+  ASSERT_STREQ(src, src_copy);
+}
+
+TEST(StrRChrTest, FindsLastCharacterThatIsNotNullTerminator) {
+  const char *src = "abcde";
+  const char *src_copy = src;
+
+  // Should return 'e' and null-terminator.
+  ASSERT_STREQ(__llvm_libc::strrchr(src, 'e'), "e");
+  // Source string should not change.
+  ASSERT_STREQ(src, src_copy);
+}
+
+TEST(StrRChrTest, FindsNullTerminator) {
+  const char *src = "abcde";
+  const char *src_copy = src;
+
+  // Should return null terminator.
+  ASSERT_STREQ(__llvm_libc::strrchr(src, '\0'), "");
+  // Source string should not change.
+  ASSERT_STREQ(src, src_copy);
+}
+
+TEST(StrRChrTest, FindsLastNullTerminator) {
+  const char src[5] = {'a', '\0', 'b', '\0', 'c'};
+  // 'b' is behind a null terminator, so should not be found.
+  ASSERT_STREQ(__llvm_libc::strrchr(src, 'b'), nullptr);
+  // Same goes for 'c'.
+  ASSERT_STREQ(__llvm_libc::strrchr(src, 'c'), nullptr);
+}
+
+TEST(StrRChrTest, CharacterNotWithinStringShouldReturnNullptr) {
+  // Since 'z' is not within the string, should return nullptr.
+  ASSERT_STREQ(__llvm_libc::strrchr("123?", 'z'), nullptr);
+}
+
+TEST(StrRChrTest, ShouldFindLastOfDuplicates) {
+  // '1' is duplicated in the string, but it should find the last copy.
+  ASSERT_STREQ(__llvm_libc::strrchr("abc1def1ghi", '1'), "1ghi");
+
+  const char *dups = "XXXXX";
+  // Should return the last occurrence of 'X'.
+  ASSERT_STREQ(__llvm_libc::strrchr(dups, 'X'), "X");
+}
+
+TEST(StrRChrTest, EmptyStringShouldOnlyMatchNullTerminator) {
+  // Null terminator should match.
+  ASSERT_STREQ(__llvm_libc::strrchr("", '\0'), "");
+  // All other characters should not match.
+  ASSERT_STREQ(__llvm_libc::strrchr("", 'A'), nullptr);
+  ASSERT_STREQ(__llvm_libc::strrchr("", '2'), nullptr);
+  ASSERT_STREQ(__llvm_libc::strrchr("", '*'), nullptr);
+}