Dlist and dip1000 challenge

Nicholas Wilson iamthewilsonator at hotmail.com
Tue Oct 23 17:18:50 UTC 2018


On Tuesday, 23 October 2018 at 15:10:24 UTC, Steven Schveighoffer 
wrote:
> I've implemented a mergesort for both slist and dlist in 
> phobos. I found it easier to start with slist, since the 
> algorithm and operation is basically the same, dlist will 
> simply have a post-sort operation that reconnects all the prev 
> pointers.
>
> I went to apply this to dlist, and found a disturbing thing -- 
> all accesses to data in dlist are done via *casting*. The idea 
> behind it is, we only store non-templated nodes inside a list, 
> and those nodes only have prev and next pointers. Then you cast 
> to the correct "PayNode" type, giving you the actual data. 
> Things are allocated properly, so it works, but holy crap, what 
> a mess. For those who are interested, here is the original PR 
> that introduced this: https://github.com/dlang/phobos/pull/2457.
>
> I decided, I'll make a PR to undo all that (the savings from 
> doing this can't be worth it, the only thing that's 
> non-templated is the range popFront and popBack), but I've now 
> run into an issue with dip1000. Apparently, some of the casting 
> confuses the compiler sufficiently enough that it can't track 
> lifetimes, and it just rubber-stamps it (at least, that's my 
> theory).
>
> I've removed the "BaseNode" type, and just use "PayNode" 
> everywhere. All of a sudden, things become un- at safe.
>
> So I started slapping @safe tags on to see where the issue is. 
> It starts with something I've known is an issue for a long 
> time, and that is having a scoped array of strings (or other 
> reference types). You get this with a type-safe variadic 
> function.
>
> The compiler treats all the array items as if they were scope, 
> meaning you can't assign a string, either allocated from the 
> heap or a literal, to things that aren't scope, which doesn't 
> make any sense. Sure the array is scope, but not what the 
> elements point at!
>
> In any case, I created a mock-up of the parts that are not 
> working, can anyone find either an issue we can file for 
> dip1000 or a way to solve this properly? I found I can mark 
> stuff trusted, but I *really* don't like that. It's not much 
> worse than casting everything, however.
>
> Here is the mockup code:
> https://run.dlang.io/is/6xDFnr
>
> I've marked main @safe, and the problematic function @safe (if 
> you don't mark the problematic function @safe, it just 
> complains that main can't do anything).
>
> Note that in reality everything here is perfectly safe, I'm not 
> escaping anything.
>

My hunch (having looked at the source) would be that this is 
because a "value" to the compiler starts out not scope and must 
be proved to be scope. In

tail.next = allocate(stuff.front, tail);

there is an inductive step the compiler would need to make to 
infer tail as scope and that goes against the requirement to 
prove the scopeness of tail (with @safe the goal is to not have 
false positives, false negatives, like this, are annoying but 
fine). Please do add a bugziliqa for this even if it proves to be 
intractable to solve. We can at least document what the compiler 
can't infer.

> So, here is one other thing I want to say. This took me HOURS 
> to find, and narrow down. Not because I don't understand the 
> concepts behind dip1000, but because the compiler has fully 
> inserted so many hidden scopes, I don't know what the actual 
> code it's compiling is. One big problem I think with dip1000 is 
> simply that it's nearly impossible to understand where the 
> issues are. Like I said at the end of the post above, the 
> result of allowing compiler inference of dip1000 is that your 
> whole program is simply marked unsafe, and you have absolutely 
> no idea where it is. You can't even guess, because scope just 
> shows up where you never typed it. Given that you NEED this 
> functionality on templates, it's going to result, IMO, in 
> people either not using dip1000, or giving up and adding 
> @trusted: to the top of their file. This is going to be 
> horrible if we can't find a way to either require scope instead 
> of inferring it in some cases, or create a way to diagnose 
> where the blasted problem actually is. Maybe something to say 
> "I expected this call to be @safe, why isn't it".
>

I totally agree.

Plug for https://github.com/dlang/dlang.org/pull/2453
We really need to better document this stuff.




More information about the Digitalmars-d mailing list