dplyr issue with dictionary size

[lionel-]

tidyverse/dplyr#5291

[DavisVaughan]

I took a look at this, and it looks like we overflow a R_len_t here

vctrs/src/dictionary.c

Line 284 in f2f02a4

R_len_t size = ceil2(vec_size(x) / 0.77);

For example, with vec_size(x) of 1e9 as used in the original issue, the closest power of 2 is 2^31, which is OOB for ints

> 1e9 / .77
[1] 1298701299
> (2 ^ 30) < (1e9 / .77)
[1] TRUE
> (2 ^ 31) < (1e9 / .77)
[1] FALSE
> as.integer(2 ^ 31)
[1] NA
Warning message:
NAs introduced by coercion to integer range 
> 2 ^ 31
[1] 2147483648

This size is stored in the dict as d->size which is a uint32_t. I thought about just making sure that we store this instead as a uint64_t, but I don't think it is that simple. The hash values are all uint32_t, and we mix the hash with k here to get a probe which would have to be uint64_t. I think that would probably break things

vctrs/src/dictionary.c

Lines 316 to 321 in f2f02a4

	uint32_t hash = x->hash[i];
	// Quadratic probing: will try every slot if d->size is power of 2
	// http://research.cs.vt.edu/AVresearch/hashing/quadratic.php
	for (uint32_t k = 0; k < d->size; ++k) {
	uint32_t probe = (hash + k * (k + 1) / 2) & (d->size - 1);

It seems like the first step to fix this if we stayed with the dictionary approach would be to change hash.c to return uint64_t hash values