reverts "[libc++] Explicitly reject `uniform_int_distribution<bool>` and `<char>`."

[cjdb]

Summary

[rand.req.genl/p1.5][1] states that template type parameters with the
name IntType are undefined if the type isn't an integer of at least
two bytes. It does not state that a program is ill-formed. This means
that it's a conforming extension for libc++ to support single-byte
integer types.

libc++ has supported this extension at least as far back as Clang 5,
regardless of developer intentions. As such, we're subject to Hyrum's
Law, and D114920 has unnecessarily and unforgivingly broken a fair
amount of user code. If libc++ has a genuine reason not to support
this extension, it should deprecate the extension and provide users with
both an explanation and a deadline, instead of abruptly flipping a
switch.

Adds test to improve confidence in these types being supported.

This reverts commit a3255f219a861fd91423def693e1b3ab3e012bec.

[1]: http://eel.is/c++draft/rand#req.genl-1.5

[manojgupta]

Thanks Christopher,

I am not sure of the rationale for the original patch. But it has caused wide spread breakages. When trying to fix them e.g,. by using uint16_t instead of unit8_t, the obvious question from code owners is why C++ can't or does not want support it?
So if there is not too much burden in supporting it, I'd appreciate that .

[ldionne]

http://eel.is/c++draft/rand.req.genl#1 says that the effect of instantiating one of these templates with a type that isn't in <list-of-allowed-types> is undefined. That means it's undefined behavior, and we strive to catch cases where users rely on undefined behavior for various reasons, notably to make their code more portable (https://godbolt.org/z/E6oGjfjhP), but also because we can't guarantee what the behavior is for such inputs.

broken a fair amount of user code.

When I tried this change internally, I did see a few breakages, but all of them were really easy to fix and made the code better. I'm curious to hear about your experience.

If you'd like to pursue this change, what I'd support is adding a escape hatch such that __libcpp_random_is_valid_inttype<T>::value is always true, and removing that after LLVM 15 has been shipped. This won't really change the fact that user's code needs to be fixed, but it will give them a bit more time to procrastinate on doing it. If that helps, I'm OK with that approach.

[cjdb]

In D125283#3506131, @ldionne wrote:

http://eel.is/c++draft/rand.req.genl#1 says that the effect of instantiating one of these templates with a type that isn't in <list-of-allowed-types> is undefined. That means it's undefined behavior, and we strive to catch cases where users rely on undefined behavior for various reasons, notably to make their code more portable (https://godbolt.org/z/E6oGjfjhP), but also because we can't guarantee what the behavior is for such inputs.

Yes, it's undefined, which means that the standard places no requirements on an implementation. That means that implementations are allowed to treat this as an extension point. libc++ can absolutely guarantee the behaviour for such inputs, because it is the implementation. Choosing to not support it is certainly a valid option, but choosing to not support it after years of having done so is incredibly user-hostile.

As for portability:

• libstdc++ accepts this code. Have you considered trying to get Microsoft/STL to adopt supporting all integer types instead of limiting the usability in libc++? That would be far more productive and would not be user-adverse.
• libc++ has plenty of extension points, and if I recall correctly, some of them aren't even opt-outable (such as choosing to continue permitting uniform_int_distribution<__int128>).

broken a fair amount of user code.

When I tried this change internally, I did see a few breakages, but all of them were really easy to fix and made the code better. I'm curious to hear about your experience.

If you'd like to pursue this change, what I'd support is adding a escape hatch such that __libcpp_random_is_valid_inttype<T>::value is always true, and removing that after LLVM 15 has been shipped. This won't really change the fact that user's code needs to be fixed, but it will give them a bit more time to procrastinate on doing it. If that helps, I'm OK with that approach.

@CrystalSplitter can provide you with data points on how ChromeOS has been affected.

[CrystalSplitter]

Hello.

I am on the ChromeOS C++ Toolchain team. I don't really interact much with the LLVM community personally, but nonetheless my work is quite affected by upstream LLVM changes. In this particular case, I'm the one who's cleaning up all the ChromeOS cases where this previous extension is used.

ChromeOS uses a lot of randomisation in tests. Notably, fuzzing frequently uses randomly generated bytes, and passing those around as bags of bytes to identify stability and security issues. It's not uncommon that uniform_int_distribution<uint8_t> or uniform_int_distribution<char> is used to generate these inputs.
Is this undefined? Yes! But it's also reliably worked up until now and is a valid extension. People are depending on this extension, regardless of whether they were aware it was an extension in the first place. They are all trivial to fix on a line-by-line difference, but it adds a burden when there are 30+ cases which all have different maintainers that one must collaborate with to get dependencies to compile. This list is still growing, because we haven't finished our investigation of how badly this breaks us.

This frustration is further fueled by the thought: Well, why isn't there support for it? There's no random algorithm which can generate a uniform random 16bit number but not a uniform random 8bit number. The implementation certainly isn't restricting us, and there's no added maintenance cost in doing so. I must then go and explain to maintainers that, while there's no technical reason this is a compiler error, we must change all the instantiations because this behaviour is not defined by the standard for ineffable reasons.

Some obvious public (still unfixed) examples in ChromeOS:

https://source.chromium.org/chromiumos/chromiumos/codesearch/+/main:src/aosp/system/update_engine/payload_generator/ab_generator_unittest.cc;l=68
https://source.chromium.org/chromiumos/chromiumos/codesearch/+/main:src/aosp/system/update_engine/payload_generator/delta_diff_utils_unittest.cc;l=198
https://source.chromium.org/chromiumos/chromiumos/codesearch/+/main:src/platform2/vm_tools/pstore_dump/persistent_ram_buffer_test.cc;l=30
https://source.chromium.org/chromiumos/chromiumos/codesearch/+/main:src/aosp/frameworks/native/services/surfaceflinger/tests/SurfaceInterceptor_test.cpp;l=454

This doesn't just affect ChromeOS notably. Here are some examples from Android:

https://cs.android.com/android/platform/superproject/+/master:external/ComputeLibrary/tests/validation/fixtures/ReductionOperationFixture.h;l=81
https://cs.android.com/android/platform/superproject/+/master:external/ComputeLibrary/tests/validation/fixtures/ConvolutionFixture.h;l=52
https://cs.android.com/android/platform/superproject/+/master:hardware/interfaces/biometrics/face/1.0/vts/functional/VtsHalBiometricsFaceV1_0TargetTest.cpp;l=196
https://cs.android.com/android/platform/superproject/+/master:external/pigweed/pw_tokenizer/generate_decoding_test_data.cc;l=220

[Mordante]

libcxx/include/__random/binomial_distribution.h

30

If we decide to reenable this can you add comments to the class what we accept bool and char as an extension. That would avoid future confusion.

Still we first need to decide whether or allow the extension.

[ldionne]

@cjdb @CrystalSplitter I understand your frustration with something that "used to work" and doesn't anymore. My main concern is that there must be a reason why these types are disallowed in the first place -- did you try to investigate why there was such a restriction in the Standard in the first place? If you do, perhaps we can use the result of that investigation to better inform on whether we should support that extension (or just lift it and change the Standard).

[cjdb]

In D125283#3507460, @ldionne wrote:

@cjdb @CrystalSplitter I understand your frustration with something that "used to work" and doesn't anymore. My main concern is that there must be a reason why these types are disallowed in the first place -- did you try to investigate why there was such a restriction in the Standard in the first place? If you do, perhaps we can use the result of that investigation to better inform on whether we should support that extension (or just lift it and change the Standard).

These types were never disallowed. If they were disallowed, then we would have either a _Mandates_ or _Constraints_ paragraph, or wording that uses the terms "ill-formed" or "ill-formed, no diagnostic required". We instead have "undefined", which translates to "behavior for which this document imposes no requirements [Note 1 ... Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message)..." (emphasis mine). In other words, so long as we document the behaviour, we can define it as valid in some fashion. As it stands, the implementation of uniform_int_distribution is inconsistent with your concern: it is also undefined to support __int128, yet it's documented as being supported.

Prior to making this CL we looked at N1398, N1452, a few in the lineage of N2111, and LWG2326. None of this seems to explain why neither single-byte nor extended integral types are undefined.

[EricWF]

GCC ships this as an extension. I can't find a reason why the extension would be non-conforming or dangerous, and it seems like a safer way for users to generate char values, rather than expecting the user to correctly pass the numerical_limits<char>::max() to the constructor.
I think we should reach out to someone at Microsoft (maybe STL), and see how open they are to shipping this as an extension. If they're willing then we avoid the portability trap that we're trying to protect users from.

[ldionne]

In D125283#3528195, @EricWF wrote:

GCC ships this as an extension. I can't find a reason why the extension would be non-conforming or dangerous, and it seems like a safer way for users to generate char values, rather than expecting the user to correctly pass the numerical_limits<char>::max() to the constructor.
I think we should reach out to someone at Microsoft (maybe STL), and see how open they are to shipping this as an extension. If they're willing then we avoid the portability trap that we're trying to protect users from.

@CaseyCarter Would you be willing to, as an extension, support char in the random distributions? This is currently marked as being undefined by http://eel.is/c++draft/rand.req.genl#1. If you are willing, then I could also write a short paper to suggest adding it to the spec, since all three major implementations would support it.

[cjdb]

In D125283#3531777, @ldionne wrote:

In D125283#3528195, @EricWF wrote:

GCC ships this as an extension. I can't find a reason why the extension would be non-conforming or dangerous, and it seems like a safer way for users to generate char values, rather than expecting the user to correctly pass the numerical_limits<char>::max() to the constructor.
I think we should reach out to someone at Microsoft (maybe STL), and see how open they are to shipping this as an extension. If they're willing then we avoid the portability trap that we're trying to protect users from.

@CaseyCarter Would you be willing to, as an extension, support char in the random distributions? This is currently marked as being undefined by http://eel.is/c++draft/rand.req.genl#1. If you are willing, then I could also write a short paper to suggest adding it to the spec, since all three major implementations would support it.

I'm not sure why there's so much resistance to reverting. libc++:

1. has users with broken code right now;
2. actively supports uniform_int_distribution<__int128_t>, which is also undefined (I don't get why you consider signed char, unsigned char, char, and bool to be problematic, but not __int128_t and unsigned __int128_t);
3. has licence to make it an extension without Microsoft/STL's support;

You can also propose standardising this right now.

[ldionne]

In D125283#3532818, @cjdb wrote:

I'm not sure why there's so much resistance to reverting. libc++:

1. has users with broken code right now;
2. actively supports uniform_int_distribution<__int128_t>, which is also undefined (I don't get why you consider signed char, unsigned char, char, and bool to be problematic, but not __int128_t and unsigned __int128_t);
3. has licence to make it an extension without Microsoft/STL's support;

You can also propose standardising this right now.

I don't know whether our distributions actually work with these types. This explicit rejection was added in D114920, which was itself prompted by discussions on D114129, whose goal was to fix http://llvm.org/PR51520 (an overflow in uniform_int_distribution<__int128_t>). What tells us that we don't have similar problems with uniform_int_distribution<char> & friends. They are not tested, so anything is possible. Then, add the fact that the Standard made those undefined, which I consider a red flag; without diving into the implementation of those distributions, I'm thinking there might be a good reason why they didn't require implementations to support those types, e.g. maybe the usual algorithms don't work properly for types of that size.

So, given this uncertainty, I think it's better for everyone (our users especially) to get this compile-time error. However, if this patch showed that our implementation indeed supports these types properly, it would become a simple question of "do we want to support them as an extension, like we do for __int128_t", and that's easier to answer.

If you can add tests to show that distributions work with these types, I'd be OK with that. We still have until June 8th to cherry-pick to LLVM 14, so we could even backport to LLVM 14 and avoid breaking users for just one release (which would be very annoying indeed).

[EricWF]

In D125283#3535047, @ldionne wrote:

If you can add tests to show that distributions work with these types, I'd be OK with that. We still have until June 8th to cherry-pick to LLVM 14, so we could even backport to LLVM 14 and avoid breaking users for just one release (which would be very annoying indeed).

Given the poor state of testing for the current random implementation, and given that writing really really high quality tests to prove the disctributions is hard, can you say what level of testing you would find sufficient?

Could we simply instantiate the type, get some results, maybe validate them *maybe*, with the intention of letting sanitizers find any overflows or UB?

[cjdb]

In D125283#3535047, @ldionne wrote:

In D125283#3532818, @cjdb wrote:

I'm not sure why there's so much resistance to reverting. libc++:

1. has users with broken code right now;
2. actively supports uniform_int_distribution<__int128_t>, which is also undefined (I don't get why you consider signed char, unsigned char, char, and bool to be problematic, but not __int128_t and unsigned __int128_t);
3. has licence to make it an extension without Microsoft/STL's support;

You can also propose standardising this right now.

I don't know whether our distributions actually work with these types. This explicit rejection was added in D114920, which was itself prompted by discussions on D114129, whose goal was to fix http://llvm.org/PR51520 (an overflow in uniform_int_distribution<__int128_t>). What tells us that we don't have similar problems with uniform_int_distribution<char> & friends. They are not tested, so anything is possible. Then, add the fact that the Standard made those undefined, which I consider a red flag; without diving into the implementation of those distributions, I'm thinking there might be a good reason why they didn't require implementations to support those types, e.g. maybe the usual algorithms don't work properly for types of that size.

So, given this uncertainty, I think it's better for everyone (our users especially) to get this compile-time error. However, if this patch showed that our implementation indeed supports these types properly, it would become a simple question of "do we want to support them as an extension, like we do for __int128_t", and that's easier to answer.

If you can add tests to show that distributions work with these types, I'd be OK with that. We still have until June 8th to cherry-pick to LLVM 14, so we could even backport to LLVM 14 and avoid breaking users for just one release (which would be very annoying indeed).

If there's a technical reason why single byte integers can't be used in the algorithms, then it's definitely possible to make specialisations that do two-byte distributions and then contract to a single-byte type.

[cjdb]

adds test to improve confidence

[cjdb]

re-adds header to modulemap, fixes test to work in C++03 mode (apparently lambdas aren't backported)

[ldionne]

In D125283#3535124, @EricWF wrote:

In D125283#3535047, @ldionne wrote:

If you can add tests to show that distributions work with these types, I'd be OK with that. We still have until June 8th to cherry-pick to LLVM 14, so we could even backport to LLVM 14 and avoid breaking users for just one release (which would be very annoying indeed).

Given the poor state of testing for the current random implementation, and given that writing really really high quality tests to prove the disctributions is hard, can you say what level of testing you would find sufficient?

Whatever level of testing we have right now for other non-char non-bool types. It seems that this is what @cjdb is doing here, so that sounds reasonable to me (except we are missing tests for a couple distributions in this patch as commented).

libcxx/include/__random/binomial_distribution.h

28

Since we are removing the restriction for these distributions too, we should also be adding tests for their behavior.

libcxx/include/__random/uniform_int_distribution.h

242–244

I don't think I understand how this works for bool. Since anything non-0 will end up being considered true and only 0 is false, how do we achieve a uniform distribution by casting a uniformly-distributed unsigned char back to bool? Am I misunderstanding something?

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/eval.pass.cpp

114–115

Should that type be bool? You're getting bool out of dist(gen), aren't you?

[cjdb]

libcxx/include/__random/binomial_distribution.h

28

I'd do so if the tests checked short, etc. were valid, but I don't think it's my responsibility to fill out the tests when they don't check all standard-required patterns. Each of the things I haven't touched only test int and one of long or long long.

libcxx/include/__random/uniform_int_distribution.h

242–244

Good question, I don't have an answer. I can increase my sample size to boost confidence that the distribution is roughly uniform, if you'd like.

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/eval.pass.cpp

114–115

It can be bool, but it doesn't need to be. I didn't want to get yelled at for using the almost universally-hated vector<bool>.

[manojgupta]

libcxx/include/__random/uniform_int_distribution.h

242–244

Shouldn't just checking for lowest bit ( val & 0x1) work for bool uniform distribution?

[ldionne]

libcxx/include/__random/binomial_distribution.h

28

I think it's easier to forget about the fact that this code used to work by accident. With that in mind, what this patch effectively does is *add* a brand new extension (that we will document and support officially) for additional types in binomial_distribution & friends. What I'm saying is that this new extension needs to be tested, just like we test everything else in the library. Otherwise, we don't have a way to make sure that we support it properly, and that's one of the reason why we made sure that people would not use it by accident (by adding static_asserts).

I'm not asking that you improve the overall test coverage for the distributions on other standard-mandated types (although that would certainly be nice). Our testing of distributions is very light, and that's a shame. What I'm asking is to meet the bar that we have for all patches: that you test the new patterns that we did not officially support previously and that we will support going forward.

libcxx/include/__random/uniform_int_distribution.h

242–244

I just re-read the implementation and I think I get it, and I think it works. It's actually pretty simple -- we'll end up generating a discrete uniform distribution on unsigned char between 0 and 1, so that maps directly to false and true. Somehow I had in mind that we were generating a distribution from 0 to numeric_limits<unsigned char>::max(), which would not have worked.

libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/eval.pass.cpp

114–115

This comment tied into my comment above about how the distribution is generated. If a distribution on 0, numeric_limits<unsigned char>::max() was generated instead and the result type was char instead of bool, this test would pass even though it should not. So I think it'd be better to use bool here, if only to show that we're really getting a bool out of the distribution.

[cjdb]

replaces vector<signed char> with vector<bool>

[cjdb]

libcxx/include/__random/binomial_distribution.h

28

I think it's easier to forget about the fact that this code used to work by accident. With that in mind, what this patch effectively does is *add* a brand new extension

No, it's not adding a brand new extension. libc++ has always supported this, regardless of the library's intention. That's how Hyrum's Law works.

Both Chrome OS and Android have been severely and adversely impacted by the changes made by D114920, which is why I'm trying to revert it. We were given no warning and no window of opportunity to change anything and have had the rug pulled out from under us. I am simply trying to unbreak the scores of packages that are using this as a result of this "accident", and would appreciate libc++ taking responsibility for the problems that D114920 has caused our teams.

I'm not asking that you improve the overall test coverage for the distributions on other standard-mandated types

That's exactly what's being asked here. You don't have the tests for short, unsigned int, etc., and in order for me to add tests for unsigned char and friends, I will need to do this very thing.

The lack of tests for supported code is indeed a shame, and it's the responsibility of libc++ developers to ensure that libc++ code is tested. I encourage libc++ contributors to take some time out to improve the tests for binomial_int_distribution and friends, but again, D125283 is a rollback of a patch that breaks downstream users who were not broken prior to this patch.

libcxx/include/__random/uniform_int_distribution.h

242–244

Sounds like I can close this thread out.

[ldionne]

libcxx/include/__random/binomial_distribution.h

28

libc++ has always supported this, regardless of the library's intention. That's how Hyrum's Law works.

It's not because something compiles that it's supported or fine to use, and I don't think it's fair to invoke Hyrum's Law to pretend the contrary here. For instance, you can do all kinds of things like use std::sort with a non-strict-weak-ordering and it will compile, yet it's UB and it's clearly not something support. Have people been doing it and getting away with results that work for them? Definitely, in some cases. That's exactly what I'm worried about here, and that's why I want this to be tested. I don't want to allow something to compile if we don't know that it works properly -- that wouldn't be responsible for our users. In other words, I'd rather break some code than silently let code compile yet maybe be wrong, especially since we know this has happened in the past in this very area of the code.

it's the responsibility of libc++ developers to ensure that libc++ code is tested

With respect, this isn't a great way to engage with the project. This is an open source project, and we accept contributions based on their technical merit and their correctness. We do our very best to cater to our users needs, because that makes the project relevant. However, you seem to imply that libc++ (or its contributors) have a responsibility to answer to the needs of specific users, and I don't think that's right. ChromeOS is using something that is officially undefined in the Standard -- it's not libc++'s problem, really, and the adversarial mentality taken by this patch isn't the best way to fix things. If you didn't want to do the work, even just a comment on D114920 explaining the situation faced by ChromeOS would have been better, because we would have been in a situation to collaboratively find a solution instead of starting with the assertion that libc++ did something wrong.

I don't think it's useful to continue this thread. I went ahead and created a patch that should address the issues encountered by ChromeOS while increasing the consistency and test coverage of libc++: https://reviews.llvm.org/D126823. If you are OK with the direction taken in D126823, I think this patch can be abandoned.

Also, I was mistaken when I said this had shipped in LLVM 14 -- it has not, so we don't need to cherry-pick anything once this is fixed.

[cjdb]

libcxx/include/__random/binomial_distribution.h

28

it's the responsibility of libc++ developers to ensure that libc++ code is tested

With respect, this isn't a great way to engage with the project. This is an open source project, and we accept contributions based on their technical merit and their correctness. We do our very best to cater to our users needs, because that makes the project relevant. However, you seem to imply that libc++ (or its contributors) have a responsibility to answer to the needs of specific users, and I don't think that's right. ChromeOS is using something that is officially undefined in the Standard -- it's not libc++'s problem, really, and the adversarial mentality taken by this patch isn't the best way to fix things. If you didn't want to do the work, even just a comment on D114920 explaining the situation faced by ChromeOS would have been better, because we would have been in a situation to collaboratively find a solution instead of starting with the assertion that libc++ did something wrong.

I understand that you're not interested in continuing the discussion, and I largely agree, but I do need to set the record straight on one thing. In its full context, the nested quote is not saying "take this patch and add the tests yourselves", which is how it is being framed here. I doubt you intentionally framed it this way, but the snippet comes across as hostile in isolation nonetheless. It's also not saying that libc++ is beholden to specific users. More explicitly, there are four key points that I was trying to communicate:

1. the tests for binomial_int_distribution are lacking (which sucks),
2. that adding comprehensive tests for binomial_int_distribution<bool>, etc., would be the same as adding comprehensive tests for binomial_int_distribution<short>, etc.,
3. that I believe adding comprehensive tests for binomial_int_distribution<short>, etc., is a responsibility for libc++ regulars, and
4. that adding such tests are beyond the scope of a revert.

In future, as requested, I'll comment on merged patches rather than proposing reverts.

If you are OK with the direction taken in D126823, I think this patch can be abandoned.

A forward-fix is also fine. @CrystalSplitter has provided commentary on D126823, since they're directly familiar with the pain points.