[libc][docs] Add doc for libc string functions

[michaelrj]

Summary

This patch adds a document describing the status of the string functions
in LLVM-libc.

[jeffbailey]

Thanks for doing this! I do want to pull all of the impllemented/unimplemented functions into a list like the C++ folks have it, but this is nice to have.

It would also be nice to check to see if the _s functions are still being considered for removal and include that information here. http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1967.htm

[gchatelet]

libc/docs/strings.rst

35–41

Outside of Google EXEgesis mostly refers to llvm-exegesis. It is not really connected to string functions (even though it's been developed by the same people).
Maybe call the section Primary memory function without description and leave the TODO assigned to me (omitting the exegesis word).

45

In this document, the Designed and Implemented columns are always equal. Maybe there is more value in telling which architectures are actually implemented ?

104

Maybe this should go into an Additional Functions section?

[michaelrj]

addressed comments.

libc/docs/strings.rst

45

Most of these string functions are completely platform independent, since they work on individual bytes at a time, so giving all of them architecture specific statuses feels redundant. On the other hand, the memory functions and the conversion functions do have possible platform differences, so tracking them could be helpful. I think the biggest problem is that all of these functions already have versions for all of our supported platforms, so no matter how we slice it the table will just say "Done" everywhere, except for the functions that we haven't started.

104

I like them here because it puts them before the functions that aren't implemented yet.

[sivachandra]

libc/docs/strings.rst

45

Perhaps a more useful way to present this is to just say whether an implementation is available or not. So, just one column Available under which you say YES if available, nothing if not. You can potentially add a Notes column in future to add additional notes if required. For a reader not involved in the development, that something has been designed or not does not help much. A person interested in contributing can engage on discourse et al to gather more information.

[gchatelet]

libc/docs/strings.rst

45

Yep in that case a single column is enough.

[michaelrj]

address comments and add performance information

[michaelrj]

add more specifics on performance comparison

[sivachandra]

Still LGTM with the suggested inline fix.

libc/docs/strings.rst

84

s/Designed/Available everywhere?

[tschuett]

In D123645#3452505, @sivachandra wrote:

Still LGTM with the suggested inline fix.

Did you say something about endianness? Or is it X86 + aarch64 only?

[michaelrj]

address final comments

libc/docs/strings.rst

84

I went with Available over Available Everywhere since it allows for specifying which platforms it is available on if that's not everywhere.

[sivachandra]

libc/docs/strings.rst

84

Ah, I didn't quite understand when @tschuett made that comment. I did not intend to suggest replacing "Designed" with "Available everywhere" but was trying to say the "Designed" should be replaced with "Available" everywhere relevant.

libc/docs/index.rst

.. toctree::
     ground_truth_specification
     header_generation
     implementation_standard
     api_test
     layering
     mechanics_of_public_api
     redirectors
     source_layout
+    strings

libc/docs/strings.rst

+=============================
+String Functions in LLVM-libc
+=============================
+
+-------
+Summary
+-------
+
+This site tracks the status of the implementation of string functions in LLVM
+Libc. This includes a few extra functions that are not in string.h, such as
+functions converting strings to numbers.
+
+---------------
+Source location
+---------------
+
+-   The main source for string functions is located at:
+    ``libc/src/string``.
+
+-   The source for string conversion functions is located at:
+    ``libc/src/stdlib`` and
+    ``libc/src/__support``.
+
+-   The tests are located at:
+    ``libc/test/src/string``,
+    ``libc/test/src/stdlib``, and
+    ``libc/test/src/__support``
+    respectively.
+
+---------------------
+Implementation Status
+---------------------
+
+Primary memory functions
+========================
+
+.. TODO(gchatelet): add details about the memory functions.
+
+
+=============  ========
+Function Name  Designed
+=============  ========
+bzero          YES
+bcmp           YES
+memcpy         YES
+memset         YES
+memcmp         YES
+memmove        YES
+=============  ========
+
+
+Other Raw Memory Functions
+==========================
+
+=============  ========
+Function Name  Designed
+=============  ========
+memchr         YES
+memrchr        YES
+memccpy        YES
+mempcpy        YES
+=============  ========
+
+String Memory Functions
+=======================
+
+=============  ========
+Function Name  Designed
+=============  ========
+stpcpy         YES
+stpncpy        YES
+strcpy         YES
+strncpy        YES
+strcat         YES
+strncat        YES
+strdup         YES
+strndup        YES
+=============  ========
+
+String Examination Functions
+============================
+
+=============  ========
+Function Name  Designed
+=============  ========
+strlen         YES
+strnlen        YES
+strcmp         YES
+strncmp        YES
+strchr         YES
+strrchr        YES
+strspn         YES
+strcspn        YES
+strpbrk        YES
+strstr         YES
+strtok         YES
+strtok_r       YES
+=============  ========
+
+String Conversion Functions
+============================
+
+These functions are not in strings.h, but are still primarily string
+functions, and are therefore tracked along with the rest of the string
+functions.
+
+The String to float functions were implemented using the Eisel-Lemire algorithm 
+(read more about the algorithm here: `The Eisel-Lemire ParseNumberF64 Algorithm
+<https://nigeltao.github.io/blog/2020/eisel-lemire.html>`_). This improved
+the performance of string to float and double, and allowed it to complete this
+comprehensive test 15% faster than glibc: `Parse Number FXX Test Data
+<https://github.com/nigeltao/parse-number-fxx-test-data>`_. The test was done 
+with LLVM-libc built on 2022-04-14 and Debian GLibc version 2.33-6. The targets
+``libc_str_to_float_comparison_test`` and 
+``libc_system_str_to_float_comparison_test`` were built and run on the test data
+10 times each, skipping the first run since it was an outlier.
+
+
+=============  ========
+Function Name  Designed
+=============  ========
+atof           YES
+atoi           YES
+atol           YES
+atoll          YES
+strtol         YES
+strtoll        YES
+strtoul        YES
+strtoull       YES
+strtof         YES
+strtod         YES
+strtold        YES
+strtoimax      YES
+strtoumax      YES
+=============  ========
+
+String Error Functions
+======================
+
+=============  ========
+Function Name  Designed
+=============  ========
+strerror
+strerror_s
+strerrorlen_s
+=============  ========
+
+Localized String Functions
+==========================
+
+These functions require locale.h, and will be added when locale support is 
+implemented in LLVM-libc.
+
+=============  ========
+Function Name  Designed
+=============  ========
+strcoll
+strxfrm
+=============  ========
+
+---------------------------
+\<name\>_s String Functions
+---------------------------
+
+Many String functions have an equivalent _s version, which is intended to be
+more secure and safe than the previous standard. These functions add runtime
+error detection and overflow protection. While they can be seen as an
+improvement, adoption remains relatively low among users. In addition, they are
+being considered for removal, see 
+`Field Experience With Annex K — Bounds Checking Interfaces
+<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1967.htm>`_. For these reasons, 
+there is no ongoing work to implement them.

libc/test/src/__support/CMakeLists.txt

add_executable(
   str_to_float_comparison_test.cpp
 )
 
 target_link_libraries(libc_str_to_float_comparison_test
   PRIVATE
     llvmlibc
 )
 
+add_executable(
+  libc_system_str_to_float_comparison_test
+  str_to_float_comparison_test.cpp
+)
+
 set(float_test_file ${CMAKE_CURRENT_SOURCE_DIR}/str_to_float_comparison_data.txt)
 
 add_custom_command(TARGET libc_str_to_float_comparison_test
                    POST_BUILD
                    COMMAND $<TARGET_FILE:libc_str_to_float_comparison_test> ${float_test_file}
                    DEPENDS ${float_test_file}
                    COMMENT "Test the strtof and strtod implementations against precomputed results." 
                    VERBATIM)
 
 add_subdirectory(CPP)
 add_subdirectory(File)
 add_subdirectory(OSUtil)