Trying to use the new RandomNumberGenerator protocol

random-api

(Jens Persson) #1

The following program compiles (using a recent dev snapshot) but crashes at runtime.

Note that MyRandomNumberGenerator conforms to the RandomNumberGenerator protocol even though it just has an empty body. Is this intentional, and if so, why?

struct MyRandomNumberGenerator : RandomNumberGenerator {}

var rg = MyRandomNumberGenerator()

let randomValue: UInt64 = rg.next()
print(randomValue)

As mentioned above, this compiles successfully (as a command line tool, using a recent dev snapshot) but crashes at runtime with this message on the call to rg.next():

Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3ffff8)

SE-0202 Amendment: Remove RNG's next extension methods
(Nate Cook) #2

That protocol has this requirement:

mutating func next() -> UInt64

It also has this method in an extension, that calls that requirement:

mutating func next<T: FixedWidthInteger & UnsignedInteger>() -> T

Unfortunately for compiler diagnostics, that generic version satisfies the actual requirement, but when you call it you get infinite recursion. Perhaps we should add a default implementation of the requirement with a fatalError("You must implement the 'next() -> UInt64' requirement") message so that you get some help when you run into this.


(Tino) #3

That workaround would help... but it's still a workaround, and imho it's a pity to introduce it to such a fresh API.
Would it already be to late to fix this in a way that would generate an error at compile time?
Maybe it's even feasible to detect recursion issues like this one.


(Jordan Rose) #4

@lorentey, what did you end up doing to solve this for Hashable?


(Karoy Lorentey) #5

Hashable was a different case; the mutual recursion in the default implementations of hashValue and hash(into:) was resolved by moving them into the compiler -- and we had to do that anyway, because default implementations interfere with SE-0185's automatic conformance synthesis feature.


(Joe Groff) #6

Putting a fatalError() in the default implementation may make the problem more visible at runtime, but it'd still be much nicer to catch this as a compiler error, especially because IDEs can normally help you out by auto-scaffolding protocol conformances when the set of missing requirements is known. Absent some language mechanism to suppress considering an extension method as a protocol implementation, it doesn't seem unreasonable to me to consider renaming the next() requirement here to something like nextWord(). In this case doing so wouldn't even really impact the user interface for next(), since the generic form would continue to work with UInt64 by calling down to the base case.


(Karoy Lorentey) #7

We could also add a dummy parameter to next<T>() with a default value:

mutating func next<T>(of type: T.Type = T.self) -> T where T: FixedWidthInteger & UnsignedInteger

This currently prevents the compiler from matching it to the requirement, while code such as r.next() as UInt will continue to work as originally intended. (Although I'm not sure if that's a bug...)


(Jordan Rose) #8

I think we do consider that a bug, SR-4625, but I'm not sure when we'll get around to fixing it, or if it requires an Evolution proposal.


(Jens Persson) #9

I'd be interested to know why the generic next method in the extension is needed, perhaps someone familiar with the implementation can explain?

The generic next seems to be doing exactly the same thing as:

UInt8.random(in: 0 ... UInt8.max, using: &rg)
UInt16.random(in: 0 ... UInt16.max, using: &rg)
UInt32.random(in: 0 ... UInt32.max, using: &rg)
UInt64.random(in: 0 ... UInt64.max, using: &rg)

no?

Why not simply remove the generic next method in the extension and replace it with

UInt8.random(using: &rg)
UInt16.random(using: &rg)
...

Or, if it has to be a generic next method in an extension to RandomNumberGenerator, it could require that the type be given as an argument, which would solve the problem:

extension RandomNumberGenerator {

    @inlinable
    public mutating func next<T>(_ : T.Type) -> T
        where T : FixedWidthInteger, T : UnsignedInteger
    {
        ...
    }

}

?


As a sidenote, this is what it looks like when I, as I normally do, let code completion help me with the exact type signatures of the required methods of a protocol:

As can be seen, the requirement is already satisfied by the (currently) self referential method shown first in the list of completions, so the one that I want:

public mutating func next() -> UInt64

is not in the list.


(Jens Persson) #10

Another question: * snip *

EDIT: I moved this question to a separate thread.


(Ben Cohen) #11

We explicitly didn't want "full-width" random number generators directly on the integer types, given past experiences with how common arc4random() % n turns up in every-day code.

This seems like the best solution to this problem to me.


(Alejandro Alonso) #12

Wow, I did not test this case, my apologies. I've gone ahead and implemented the type argument solution, however diagnostics for a type that doesn't conform to the protocol don't seem correct.

(swift) struct RNG: RandomNumberGenerator {}
<REPL Input>:1:8: error: type 'RNG' does not conform to protocol 'RandomNumberGenerator'
struct RNG: RandomNumberGenerator {}
       ^
Swift.RandomNumberGenerator:2:37: note: candidate has non-matching type '<Self, T> (T.Type) -> T'
    @inlinable public mutating func next<T>(_ type: T.Type) -> T where T : FixedWidthInteger, T : UnsignedInteger
                                    ^
Swift.RandomNumberGenerator:3:37: note: candidate has non-matching type '<Self, T> (upperBound: T) -> T'
    @inlinable public mutating func next<T>(upperBound: T) -> T where T : FixedWidthInteger, T : UnsignedInteger
                                    ^
Swift.RandomNumberGenerator:2:26: note: protocol requires function 'next()' with type '() -> UInt64'; do you want to add a stub?
    public mutating func next() -> UInt64
                         ^
(swift) 

I'm not sure if these diagnostics will show up in something like Xcode, but this doesn't seem correct as the first two diagnostics are not useful for the user. @Joe_Groff's suggestion to rename the requirement to nextWord() however, gets us the correct diagnostics.

(swift) struct RNG: RandomNumberGenerator {}
<REPL Input>:1:8: error: type 'RNG' does not conform to protocol 'RandomNumberGenerator'
struct RNG: RandomNumberGenerator {}
       ^
Swift.RandomNumberGenerator:2:26: note: protocol requires function 'nextWord()' with type '() -> UInt64'; do you want to add a stub?
    public mutating func nextWord() -> UInt64
                         ^
(swift)

This is a bigger workaround as it requires a name change.


(Jens Persson) #13

I agree that the two note: candidate has non-matching type ... in the diagnostics is not useful for the user in this specific case, but I think that the diagnostics are correct in general.

Also, the parts of these diagnostics that will be immediately visible in the Xcode UI are the same for both solutions, and both will suggest the fix of adding a protocol stub for the required public mutating next() -> UInt64 method, which is what we want.

The notes about the candidates with non-matching type will only show if you look in Xcode's Issue Navigator.

So as far as I can see, this should not stop the type argument solution.


(Alejandro Alonso) #14

I came across an interesting idea while trying to solve this issue. Instead of renaming one of the methods, what if we made

public mutating func next<T: FixedWidthInteger & UnsignedInteger>() -> T
// and
public mutating func next<T: FixedWidthInteger & UnsignedInteger>(upperBound: T) -> T

both internal to the standard library? Users are encouraged to use facilities such as Int.random(in:using:) anyways. Curious to hear what thoughts you guys have regarding this issue. Is this worth a full on proposal, or can I write an amendment?


(Xiaodi Wu) #15

I'm not sure what you mean here. Requirements of public protocols can't be made internal.


(Alejandro Alonso) #16

These aren't requirements of RandomNumberGenerator, only extension methods. The only requirement of RandomNumberGenerator is mutating func next() -> UInt64.


(Jens Persson) #17

How would that affect the extendability of the Random API?

(Ie, user's ability to write their own seedable pseudorandom generators, assuming a future PseudoRandomNumberGenerator protocol, the ability to add custom functionality, choosing specific ways of transforming the generated bit patterns into various types and distributions etc.)


What was the problem with the above solution:

?


(Alejandro Alonso) #18

AFAIK, this should have no effect on the extensibility of the random API.

// if you need to get a generic full width integer assuming
// T conforms to FixedWidthInteger and UnsignedInteger
let x: T = generator.next()
// with the next one, it doesn't have to be UnsignedInteger
// or
let x = T.random(in: .min ... .max, using: &generator)

It's a bit more verbose, but it's much clearer to the reader about what sort of value x.
Another example:

// if you need a number from 0 to upperBound (say 16) assuming
// T conforms to FixedWidthInteger and UnsignedInteger
let x: T = generator.next(upperBound: 16)
// with the next one, it doesn't have to be UnsignedInteger
// or
let x = T.random(in: 0 ..< 16, using: &generator)

I have a real world example. Here's the current implementation of randomElement():

public func randomElement<T: RandomNumberGenerator>(
  using generator: inout T
) -> Element? {
  guard !isEmpty else { return nil }
  let random = generator.next(upperBound: UInt(count))
  let index = self.index(
    startIndex,
    offsetBy: numericCast(random)
  )
  return self[index]
}

We can rewrite the random variable to something like:

let random = Int.random(in: 0 ..< count, using: &generator)

which lets us remove the numericCast as well.

Well, right now that solution is somewhat of a source compatibility issue. At the time I had doubts about the solution as it seemed somewhat of a hurry fix. I was so stuck on wanting to rename next() -> UInt64 for so long until I thought of this.


(Jens Persson) #19

It was a long time since I thought about this or looked at the implemenentation, so I am not really in a position to comment.

(I'm still not sure why/if those generic methods are actually needed, ie I still don't know the answer to my question above:

I assume the answer is that they are needed for the implementations of for example those random(in:, using:)-methods.)


(Alejandro Alonso) #20

Yes, these methods are primarily used for the implementations of .random(in:using:) as of right now.