[Bug libstdc++/87744] New: Some valid instantiations of linear_congruential_engine produce compiler errors when __int128 isn't available

[lrflew.coll at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87744

            Bug ID: 87744
           Summary: Some valid instantiations of
                    linear_congruential_engine produce compiler errors
                    when __int128 isn't available
           Product: gcc
           Version: 7.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: lrflew.coll at gmail dot com
  Target Milestone: ---

This issue occurs when the UIntType parameter is 64-bits, the platform being
compiled for can't use 128-bit integers (for example, 32-bit x86), and the LCG
parameters are chosen to meet certain requirements. An example of code that hit
this error is this:

#include <random>
int main() {
    std::linear_congruential_engine<unsigned long long int,
864691128455135232ULL, 12347ULL, 4052555153018976267ULL> gen;
    gen();
}

This compiles fine when __int128 is present, and fails when it isn't. When I
compile this with the -m32 flag, it prints out a lot of errors.

To summarize the problem, the error happens when determining which template
specification of _Select_uint_least_t to use in random.h. When determining how
to define operator() for the engine, it realizes that the A value is large
enough to overflow the 64-bit result type, and that the precondition for
Schrage's method isn't met (M % A > M / A). Because of this, it attempts to
find a larger integer type to use for the computation using
_Select_uint_least_t. Since the result type is already 64-bits, and the 128-bit
integer isn't available, it ends up not finding a large enough integer type,
and hits the static assert in the unspecified variant of _Select_uint_least_t.

This isn't a simple issue to resolve. The static assert that gets hit even says
"sorry, would be too much trouble for a slow result". However, as far as I can
tell, this instantiation of linear_congruential_engine is valid in the
standard, so it shouldn't result in an error. This instantiation doesn't
produce any compile errors when I tried it with MSVC, Boost, and libc++'s
implementation of linear_congruential_engine (though libc++ incorrectly uses
Schrage's method). While a solution would be slow, it's probably needed for
full standards compliance.