Possible bug in associative array implementation (and/or @safe checking)

[Steven Schveighoffer]

On 8/16/18 2:32 PM, Aaron D. Trout wrote:
> [...]
> On Thursday, 16 August 2018 at 17:20:23 UTC, Steven Schveighoffer wrote:
>>
>> Yes, this is the effect I would expect.
>>
>> D has traditionally simply allowed slicing stack data without question 
>> (even in @safe code), but that will change when dip1000 is fully 
>> realized. It will be allowed, but only when assigning to scope variables.
>>
> 
> Thanks for the quick and knowledgeable reply! I think I understand 
> what's going on, but I'm surprised it is allowed in @safe code since the 
> compiler doesn't allow the following, even in non- at safe code:
> 
> int[] badSlice()
> {
>      int[2] buffer;
>      return buffer[];
> }

It's because it's on the same line. This is a crude "safe" feature that 
is easily duped.

This is allowed to compile:

int[2] buffer;
auto buf = buffer[];
return buf;

But add -dip1000 to the dmd options and that fails.

I would warn you that I think dip1000 is too crude to start trying to 
apply it to your project, and may have linker errors with Phobos.

> I guess the compiler just isn't (yet!) able to catch that the 
> associative array is storing a slice of expired stack. I'm surprised 
> that the built-in AA implementation *allows* using slices as keys in 
> @safe code without copying the underlying data to the heap first. This 
> is clearly dangerous, but perhaps heap-copying slices defensively would 
> result in an unacceptable performance hit.

I wouldn't put too much stock in having safety in the AA. The AA is a 
very very old piece of the compiler, that pre-dates safety checks, and 
still is a bit of a kludge in terms of type and memory safety. If you do 
find any obvious bugs, it's good to report them.

> This issue came up while trying to eliminate unnecessary allocation in 
> my code. In my case, I could set a maximum key length at compile time 
> and switch my key type to a struct wrapping a static array buffer.
> 
> In hindsight, it was silly for me to think I could eliminate separately 
> allocating the keys when the key type was a variable length array, since 
> the AA must store the keys. That said, a suitable admonition from the 
> compiler here would have been very educational. I look forward to seeing 
> the full inclusion of DIP1000!

In this case, actually, the AA does NOT store the key data, but just the 
reference to the keys. An array slice is a pointer and length, and the 
data is stored elsewhere. The static version, however, does store all 
the key data inside the AA.

That being said, you can potentially avoid more allocation with the keys 
with various tricks, such as pre-allocating all the keys and then using 
the reference.

In other words, eagerly stick the data into an array of arrays:

     auto sets = setA.map!(j => setB.filter!(i => i % j == 0).array).array;

and then not worry about duping them. But it all depends on your use case.

-Steve