[C++] Add string length kernel

[asfimport]

We have "binary_length" but that doesn't handle UTF-8 the way we need for this. Example (from R):

> string <- "áéíóú"
> nchar(string)
[1] 5
> arrow:::call_function("binary_length", Scalar$create(string))
Scalar
10

cc @maartenbreddels @pitrou @jorisvandenbossche

Reporter: Neal Richardson / @nealrichardson
Assignee: Eduardo Ponce / @edponce

Related issues:

• [C++] String algorithm library for StringArray/BinaryArray (is a child of)

PRs and other links:

• GitHub Pull Request #9786

_{Note: This issue was originally created as ARROW-11693. Please see the migration documentation for further details.}

[asfimport]

Joris Van den Bossche / @jorisvandenbossche:
The binary_length was originally added as ascii_length in #7278, as a simple (example) kernel, and indeed not yet meant to specifically handle unicode logical string size, I think. Having a proper UTF8 string length kernel would indeed be good (also needed for pandas' string methods).

[asfimport]

Antoine Pitrou / @pitrou:
I'll take it unless someone else feels strongly about it :)

[asfimport]

Antoine Pitrou / @pitrou:
cc @edponce

[asfimport]

Eduardo Ponce / @edponce:
We can leverage utf8proc which is already a dependency for some string operations in compute kernel. Specifically, use the utf8proc_iterate function (https://juliastrings.github.io/utf8proc/doc/utf8proc_8h.html#a48041dd763513b314763f5b40fad50b0)

[asfimport]

Antoine Pitrou / @pitrou:
I don't think we need utf8proc. Counting UTF8 characters is simply a matter of counting bytes with the upper bit cleared

(Python pseudocode:  utf8_length(bytestring) = sum((b < 0x80) for b in bytestring))

[asfimport]

Eduardo Ponce / @edponce:
I have a utf8proc implementation, and will compare with pseudocode (I did find similar implementations while reading on UTF8).

[asfimport]

Eduardo Ponce / @edponce:
Well, thinking more about it, simply checking against 0x80 also includes invalid sequences because not all sequences in that range are valid UTF8. Consider invalid bytes, invalid continuation bytes, invalid sequence, etc. utf8proc decodes taking into consideration these cases: https://github.com/JuliaStrings/utf8proc/blob/master/utf8proc.c#L124-L171

[asfimport]

Antoine Pitrou / @pitrou:
True, but utf8 data is supposed to be valid already. I don't think we need to care about invalid sequences here.

[asfimport]

Eduardo Ponce / @edponce:
Ok, @pitrou thanks for the feedback.

[asfimport]

Antoine Pitrou / @pitrou:
Issue resolved by pull request 9786
#9786