Page MenuHomePhabricator

[libc++] Implements Unicode grapheme clustering

Authored by Mordante on Jun 3 2022, 9:10 AM.


Group Reviewers
Restricted Project
rG857a78c04dee: [libc++] Implements Unicode grapheme clustering

This implements the Grapheme clustering as required by
P1868R2 width: clarifying units of width and precision in std::format

This was omitted in the initial patch, but the paper was marked as completed. This really completes the paper.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Mordante updated this revision to Diff 434273.Jun 4 2022, 9:36 AM

Fixes ASAN errors.

Mordante updated this revision to Diff 434327.Jun 5 2022, 7:04 AM

Improves end of input handling. That should fix the CI errors.

Mordante added inline comments.Jun 5 2022, 10:52 AM

D125606 "Not specific to this diff but I think it would be cleaner to fold Unicode/non-Unicode handling into __estimate_column_width and have a single check and copy here."

Mordante updated this revision to Diff 434427.Jun 6 2022, 4:22 AM

Use a better way to store the data.
This improves the speed by 7% from the last version, and 4% from the original 6 byte algorithm.

Note the code and comment needs more polish.

Mordante updated this revision to Diff 441926.Jul 3 2022, 1:27 AM

Improve and polish the code. Replace libc++ specific tests with generic tests.

Mordante updated this revision to Diff 441945.Jul 3 2022, 5:45 AM

Fixing GCC build failures.

Mordante updated this revision to Diff 441947.Jul 3 2022, 6:25 AM

Disable a test in GCC since it times out.

Mordante updated this revision to Diff 441966.Jul 3 2022, 10:38 AM
Mordante added a subscriber: STL_MSFT.

Minor cleanups and addresses @STL_MSFT's review comments while upstreaming some of these changes.

Mordante published this revision for review.Jul 3 2022, 10:39 AM
Mordante added reviewers: ldionne, vitaut.
Herald added a project: Restricted Project. · View Herald TranscriptJul 3 2022, 10:39 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Mordante edited the summary of this revision. (Show Details)Jul 3 2022, 10:42 AM
vitaut requested changes to this revision.Jul 9 2022, 8:30 AM

Mostly looks good but at least one output doesn't look right which suggests an error in width estimation. Also a few nits inline.


Looks like this include is no longer needed since you removed the only std::array usage.


enigine -> engine


Why is __truncate in the __detail namespace while other functions which are also implementation details aren't?


Is it the last or one past the last? Seems like the latter. Also "parsed" seems a bit unclear in this context. Are you referring to grapheme clusterization as parsing? I would also recommend using a more descriptive name like __end_ or __last_.


nit: I wouldn't call it an issue. It's how width and precision work and very much expected behavior =).


with -> width


It is well-defined in the same way the Unicode standard we are referring to is well-defined. I suggest saying that it can change instead, particularly with the change to the Unicode standard.


As a potential future optimization (not in this diff) you might want to consider branchless code point decoding, e.g.


I think the output should be "*\u00a1**" because U+00A1 has an estimated width of 1:

This revision now requires changes to proceed.Jul 9 2022, 8:30 AM
Mordante marked 9 inline comments as done.Jul 9 2022, 12:23 PM

Thanks a lot for your review!


Good point there used to be more in __detail, I've removed that inner namespace.


I agree, __last_ would be a better name and consistent with other parts of the code.
I'm removed the word "parsed".


I agree it's as specified :-) I removed this entire sentence, it didn't add much information not captures in the other comment.


I removed most of this sentence and just mention the specifications in [format.string.std]/11.


This looks very interesting, thanks for the hint!


This test tests the output when using ASCII. When using ASCII the codepoint uses two bytes and thus *\u00a1* is correct. In the Unicode test the column width is estimated at one. I left a comment in that file.


@vitaut This is the unicode test where the column width is 1.

Mordante updated this revision to Diff 443456.Jul 9 2022, 12:46 PM
Mordante marked 6 inline comments as done.

Addresses review comments.

vitaut added inline comments.Jul 10 2022, 9:00 AM

Missed that, sorry. It makes sense now.

vitaut added inline comments.Jul 10 2022, 9:51 AM

"of" is missing after point




Maybe generate only one of data_utf16 and data_utf32 if the other is not used? Or are they both used?


The template operator()< part make the tests a bit difficult to parse. I would recommend passing the format string as a normal argument and not as a template parameter.

I have some comments. Being a total unicode newbie, this is mostly out of my depth, but the general approach looks sensible to me. I'll have a closer look at to provide a more meaningful review, but this basically LGTM via the assumption that the test coverage would catch issues in the implementation.

68 ↗(On Diff #441966)

This should be part of a separate patch.


// _LIBCPP_HAS_NO_UNICODE? This is quite a long #if block.


According to what you just said during live review, changes from time to time (roughly once a year). Consequently, I think we'll want to make it as easy as possible to update. As discussed, we also don't want to get automatic updates under our feet without manual intervention, because the rules might need to change, etc. Hence, I would suggest:

  1. We download the tables that you use to generate headers and tests and check them into libc++ in a reasonable location. Preferably in a subdirectory with a that explains what those are and where to download them from.
  2. We add the running of the generation scripts to libcxx-generate-files.

That way, the workflow for updating those files is simply to re-download the latest tables online, re-generate the headers+tests using libcxx-generate-files, and check that in. Furthermore, if we ever forget to re-generate the headers and tests, the CI will tell us through our existing mechanisms.


Those should be in sync!

Also, I would recommend using the latest version of these files, even though the standard uses 12.0 in its bibliography.

Mordante marked 7 inline comments as done.Wed, Jul 13, 9:28 AM

Thanks for the reviews!


They are both used. Some of our supported platforms have sizeof(wchar_t) == 16, for example Windows and AIX.


The issue is the string is used as both as char and wchar_t. In the past there was no other way to do this, at that time an approach like STATICALLY-WIDEN failed. However STATICALLY-WIDEN now seems to work with all supported compilers. However I used this approach in a lot of tests so I rather "fix" them in one go. So I'll add a todo to my list.


I've given this some more thought. Instead of making these changes in this commit I will work on a follow-up commit to make these changes. I don't see the easy way to update as a must-have for LLVM-15 since I don't intend to update these tables in the release branch. That way there's less risk for this patch to miss the branching point.


I actually used 12 for both but forgot to update this link from the Microsoft code.

But since we want to use the latest version I use the Unicode links to the latest version. That way we don't need to update the links when we update the tables.

Mordante updated this revision to Diff 444319.Wed, Jul 13, 9:56 AM
Mordante marked 2 inline comments as done.

Addresses review comments and updates the Unicode tables to version 14.

ldionne accepted this revision.Wed, Jul 20, 8:25 AM
ldionne added inline comments.

That sounds reasonable, but let's not forget to do this. It's really important to have an easy way to keep those up-to-date, or they will become stale in no time.

Mordante marked 2 inline comments as done.Wed, Jul 20, 8:53 AM

Thanks for the review!


I've already created D129668, which most likely needs more work.

This revision was not accepted when it landed; it landed in state Needs Review.Wed, Jul 20, 9:38 AM
This revision was automatically updated to reflect the committed changes.
Mordante marked an inline comment as done.

It seems one of the clang-tidy changes flags the current code. I should be able to fix this rather fast.

@abrachet I've committed a fix.