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