Walter Bright Wrote:

> Consider the code:
> 
>    @safe:
>      T[] foo(T[] a) { return a; }
> 
>      T[] bar()
>      {
>          T[10] x;
>          return foo(x);
>      }
> 
> Now we've got an escaping reference to bar's stack. This is not memory safe. But giving up slices is a heavy burden.
> 
> So it occurred to me that the same solution for closures can be used here. If the address is taken of a stack variable in a safe function, that variable is instead allocated on the heap. If a more advanced compiler could prove that the address does not escape, it could be put back on the stack.
> 
> The code will be a little slower, but it will be memory safe. This change wouldn't be done in trusted or unsafe functions.

At a fundamental level, safety isn't about pointers or references to stack variables, but rather preventing their escape beyond function scope. Scope parameters could be very useful. Scope delegates were introduced for a similar reason.

Jason House wrote:
> At a fundamental level, safety isn't about pointers or references to
> stack variables, but rather preventing their escape beyond function
> scope. Scope parameters could be very useful. Scope delegates were
> introduced for a similar reason.

The problem is, they aren't so easy to prove correct.

Walter Bright Wrote:

> Jason House wrote:
> > At a fundamental level, safety isn't about pointers or references to stack variables, but rather preventing their escape beyond function scope. Scope parameters could be very useful. Scope delegates were introduced for a similar reason.
> 
> The problem is, they aren't so easy to prove correct.

I understand the general problem with escape analysis, but I've always thought of scope input as meaning @noescape. That should lead to easy proofs. If my @noescape input (or slice of an array on the stack) is passed to a function without @noescape, it's a compile error. That reduces escape analysis to local verification.

On Thu, 12 Nov 2009 08:45:36 -0500, Jason House <jason.james.house@gmail.com> wrote:

> Walter Bright Wrote:
>
>> Jason House wrote:
>> > At a fundamental level, safety isn't about pointers or references to
>> > stack variables, but rather preventing their escape beyond function
>> > scope. Scope parameters could be very useful. Scope delegates were
>> > introduced for a similar reason.
>>
>> The problem is, they aren't so easy to prove correct.
>
> I understand the general problem with escape analysis, but I've always thought of scope input as meaning @noescape. That should lead to easy proofs. If my @noescape input (or slice of an array on the stack) is passed to a function without @noescape, it's a compile error. That reduces escape analysis to local verification.

The problem is cases like this:

char[] foo()
{
  char buf[100];
  // fill buf
  return strstr(buf, "hi").dup;
}

This function is completely safe, but without full escape analysis the compiler can't tell.  The problem is, you don't know how the outputs of a function are connected to its inputs.  strstr cannot have its parameters marked as scope because it returns them.

Scope parameters draw a rather conservative line in the sand, and while I think it's a good optimization we can get right now, it's not going to help in every case.  I'm perfectly fine with @safe being conservative and @trusted not, at least the power is still there if you need it.

-Steve

Steven Schveighoffer Wrote:

> On Thu, 12 Nov 2009 08:45:36 -0500, Jason House <jason.james.house@gmail.com> wrote:
> 
> > Walter Bright Wrote:
> >
> >> Jason House wrote:
> >> > At a fundamental level, safety isn't about pointers or references to stack variables, but rather preventing their escape beyond function scope. Scope parameters could be very useful. Scope delegates were introduced for a similar reason.
> >>
> >> The problem is, they aren't so easy to prove correct.
> >
> > I understand the general problem with escape analysis, but I've always thought of scope input as meaning @noescape. That should lead to easy proofs. If my @noescape input (or slice of an array on the stack) is passed to a function without @noescape, it's a compile error. That reduces escape analysis to local verification.
> 
> The problem is cases like this:
> 
> char[] foo()
> {
>    char buf[100];
>    // fill buf
>    return strstr(buf, "hi").dup;
> }
> 
> This function is completely safe, but without full escape analysis the compiler can't tell.  The problem is, you don't know how the outputs of a function are connected to its inputs.  strstr cannot have its parameters marked as scope because it returns them.
> 
> Scope parameters draw a rather conservative line in the sand, and while I think it's a good optimization we can get right now, it's not going to help in every case.  I'm perfectly fine with @safe being conservative and @trusted not, at least the power is still there if you need it.
> 
> -Steve

what's the signature of strstr? Your example really boils down to proving strstr is safe. You're implying that the return of buf from strstr is unsafe. Indeed, my intentionally short post didn't discuss returning from functions. Ignoring that for a moment, surely you'd agree the following is safe:

char[] foo(){
    char[100] buf;
    copystringintobuf(buf, "hi");
    return buf[0..2].dup;
}

As far as return types, there are two subtle issues:
1. Returned input argument must preserve the scope requirements of the caller. A similar problem as return variables and const annotation.
2. Unlike const annotations, there is more than three states for scope, it's simply a measure of how deep/shallowvariables can be in the stack.

On Thu, 12 Nov 2009 08:56:25 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Thu, 12 Nov 2009 08:45:36 -0500, Jason House <jason.james.house@gmail.com> wrote:
>
>> Walter Bright Wrote:
>>
>>> Jason House wrote:
>>> > At a fundamental level, safety isn't about pointers or references to
>>> > stack variables, but rather preventing their escape beyond function
>>> > scope. Scope parameters could be very useful. Scope delegates were
>>> > introduced for a similar reason.
>>>
>>> The problem is, they aren't so easy to prove correct.
>>
>> I understand the general problem with escape analysis, but I've always thought of scope input as meaning @noescape. That should lead to easy proofs. If my @noescape input (or slice of an array on the stack) is passed to a function without @noescape, it's a compile error. That reduces escape analysis to local verification.
>
> The problem is cases like this:
>
> char[] foo()
> {
>    char buf[100];
>    // fill buf
>    return strstr(buf, "hi").dup;
> }
>
> This function is completely safe, but without full escape analysis the compiler can't tell.  The problem is, you don't know how the outputs of a function are connected to its inputs.  strstr cannot have its parameters marked as scope because it returns them.
>
> Scope parameters draw a rather conservative line in the sand, and while I think it's a good optimization we can get right now, it's not going to help in every case.  I'm perfectly fine with @safe being conservative and @trusted not, at least the power is still there if you need it.
>
> -Steve

Well something like this should work (note that I'm making the conversion from T[N] to T[] explicit)

auto strstr(T,U)(T src, U substring)
    if(isRandomAccessRange!T &&
       isRandomAccessRange!U &&
       is(ElementType!U == ElementType!T)
{ /* Do strstr */ }

char[] foo() {                     // Returns type char[]
   char buf[100];                  // Of type scope char[100]
   // fill buf                     // "hi" is type immutable(char)[]
   return strstr(buf[], "hi").dup; // returns a lent char[], which is dup-ed into a char[], which is okay to return
}

char[] foo2() {                    // Returns type char[]
   char buf[100];                  // Of type scope char[100]
   // fill buf                     // "hi" is type immutable(char)[]
   return strstr(buf[], "hi");     // Error, strstr returns a lent char[], not char[].
}

lent char[] foo3() {               // Returns type lent char[]
   char buf[100];                  // Of type scope char[100]
   // fill buf                     // "hi" is type immutable(char)[]
   return strstr(buf[], "hi");     // Error, scope char[] cannot be implicitly converted to lent char[] inside a lent char[] function: possible escape.
}

char[] foo4() {                    // Returns type char[]
   char buf[100];                  // Of type scope char[100]
   return buf;                     // Error, return type is char[] not char[100].
}

char[] foo5() {                    // Returns type char[]
   char buf[100];                  // Of type scope char[100]
   return buf[];                   // Error, return type is char[] not scope char[].
}

Here's an (outdated and confusing) proposal I put together a while ago (It's pre-DIP): http://prowiki.org/wiki4d/wiki.cgi?OwnershipTypesInD In it, I used stack and scope instead of scope and lent.

Overview:

The AMD Advanced Synchronization Facility (ASF) is an experimental instruction set extension for the AMD64 architecture that would provide new capabilities for efficient synchronization of access to shared data in highly multithreaded applications as well as operating system kernels. ASF provides a means for software to inspect and update multiple shared memory locations atomically without having to rely on locks for mutual exclusion. It is intended to facilitate lock-free programming for highly concurrent shared data structures, allowing more complex and higher performance manipulation of such structures than is practical with traditional techniques based on compare-swap instructions such as CMPXCHG16B. ASF code can also interoperate with lock-based code, or with _Software Transactional Memory_.

Some basic usage examples of ASF are provided in the specification. However, we expect the programming community could readily use the power and flexibility of ASF to implement very sophisticated, robust and innovative concurrent data structure algorithms, and we encourage such experimentation. AMD will be releasing a simulation framework in the near future to facilitate this.

AMD is releasing this proposal to encourage the parallel programming community to review and comment on it. Such input will help shape the ultimate direction of this feature, so that it may best serve the needs of advanced parallel application developers.

Discussion:
http://forums.amd.com/devblog/blogpost.cfm?catid=317&threadid=114715&utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+AmdDeveloperBlogs+%28AMD+Developer+Blogs%29
 and here
http://forums.amd.com/devblog/blogpost.cfm?catid=317&threadid=118419&utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+AmdDeveloperBlogs+%28AMD+Developer+Blogs%29


The spec can be found here:

http://developer.amd.com/cpu/ASF/Pages/default.aspx


regards
Nick B

On Fri, 13 Nov 2009 05:23:08 +0300, Nick B <nick_NOSPAM_.barbalich@gmail.com> wrote:

> Overview:
>
> The AMD Advanced Synchronization Facility (ASF) is an experimental instruction set extension for the AMD64 architecture that would provide new capabilities for efficient synchronization of access to shared data in highly multithreaded applications as well as operating system kernels. ASF provides a means for software to inspect and update multiple shared memory locations atomically without having to rely on locks for mutual exclusion. It is intended to facilitate lock-free programming for highly concurrent shared data structures, allowing more complex and higher performance manipulation of such structures than is practical with traditional techniques based on compare-swap instructions such as CMPXCHG16B. ASF code can also interoperate with lock-based code, or with _Software Transactional Memory_.
>
> Some basic usage examples of ASF are provided in the specification. However, we expect the programming community could readily use the power and flexibility of ASF to implement very sophisticated, robust and innovative concurrent data structure algorithms, and we encourage such experimentation. AMD will be releasing a simulation framework in the near future to facilitate this.
>
> AMD is releasing this proposal to encourage the parallel programming community to review and comment on it. Such input will help shape the ultimate direction of this feature, so that it may best serve the needs of advanced parallel application developers.
>
> Discussion:
> http://forums.amd.com/devblog/blogpost.cfm?catid=317&threadid=114715&utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+AmdDeveloperBlogs+%28AMD+Developer+Blogs%29
>   and here
> http://forums.amd.com/devblog/blogpost.cfm?catid=317&threadid=118419&utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+AmdDeveloperBlogs+%28AMD+Developer+Blogs%29
>
>
> The spec can be found here:
>
> http://developer.amd.com/cpu/ASF/Pages/default.aspx
>
>
> regards
> Nick B

<offtopic>
Please start a new thread by clicking "Create New" button (or similar), not by replying to an existing thread. Thanks!
</offtopic>

On Thu, 12 Nov 2009 19:29:28 -0500, Robert Jacques <sandford@jhu.edu> wrote:

> On Thu, 12 Nov 2009 08:56:25 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>
>> On Thu, 12 Nov 2009 08:45:36 -0500, Jason House <jason.james.house@gmail.com> wrote:
>>
>>> Walter Bright Wrote:
>>>
>>>> Jason House wrote:
>>>> > At a fundamental level, safety isn't about pointers or references to
>>>> > stack variables, but rather preventing their escape beyond function
>>>> > scope. Scope parameters could be very useful. Scope delegates were
>>>> > introduced for a similar reason.
>>>>
>>>> The problem is, they aren't so easy to prove correct.
>>>
>>> I understand the general problem with escape analysis, but I've always thought of scope input as meaning @noescape. That should lead to easy proofs. If my @noescape input (or slice of an array on the stack) is passed to a function without @noescape, it's a compile error. That reduces escape analysis to local verification.
>>
>> The problem is cases like this:
>>
>> char[] foo()
>> {
>>    char buf[100];
>>    // fill buf
>>    return strstr(buf, "hi").dup;
>> }
>>
>> This function is completely safe, but without full escape analysis the compiler can't tell.  The problem is, you don't know how the outputs of a function are connected to its inputs.  strstr cannot have its parameters marked as scope because it returns them.
>>
>> Scope parameters draw a rather conservative line in the sand, and while I think it's a good optimization we can get right now, it's not going to help in every case.  I'm perfectly fine with @safe being conservative and @trusted not, at least the power is still there if you need it.
>>
>> -Steve
>
> Well something like this should work (note that I'm making the conversion  from T[N] to T[] explicit)
>
> auto strstr(T,U)(T src, U substring)
>      if(isRandomAccessRange!T &&
>         isRandomAccessRange!U &&
>         is(ElementType!U == ElementType!T)
> { /* Do strstr */ }
>
> char[] foo() {                     // Returns type char[]
>     char buf[100];                  // Of type scope char[100]
>     // fill buf                     // "hi" is type immutable(char)[]
>     return strstr(buf[], "hi").dup; // returns a lent char[], which is dup-ed into a char[], which is okay to return
> }
>
> char[] foo2() {                    // Returns type char[]
>     char buf[100];                  // Of type scope char[100]
>     // fill buf                     // "hi" is type immutable(char)[]
>     return strstr(buf[], "hi");     // Error, strstr returns a lent char[], not char[].
> }

Your proposal depends on scope being a type modifier, which it currently is not.  I think that's a separate issue to tackle.

-Steve

On Thu, 12 Nov 2009 18:34:48 -0500, Jason House <jason.james.house@gmail.com> wrote:

> Steven Schveighoffer Wrote:
>
>> On Thu, 12 Nov 2009 08:45:36 -0500, Jason House
>> <jason.james.house@gmail.com> wrote:
>>
>> > Walter Bright Wrote:
>> >
>> >> Jason House wrote:
>> >> > At a fundamental level, safety isn't about pointers or references  
>> to
>> >> > stack variables, but rather preventing their escape beyond function
>> >> > scope. Scope parameters could be very useful. Scope delegates were
>> >> > introduced for a similar reason.
>> >>
>> >> The problem is, they aren't so easy to prove correct.
>> >
>> > I understand the general problem with escape analysis, but I've always
>> > thought of scope input as meaning @noescape. That should lead to easy
>> > proofs. If my @noescape input (or slice of an array on the stack) is
>> > passed to a function without @noescape, it's a compile error. That
>> > reduces escape analysis to local verification.
>>
>> The problem is cases like this:
>>
>> char[] foo()
>> {
>>    char buf[100];
>>    // fill buf
>>    return strstr(buf, "hi").dup;
>> }
>>
>> This function is completely safe, but without full escape analysis the
>> compiler can't tell.  The problem is, you don't know how the outputs of a
>> function are connected to its inputs.  strstr cannot have its parameters
>> marked as scope because it returns them.
>>
>> Scope parameters draw a rather conservative line in the sand, and while I
>> think it's a good optimization we can get right now, it's not going to
>> help in every case.  I'm perfectly fine with @safe being conservative and
>> @trusted not, at least the power is still there if you need it.
>>
>> -Steve
>
> what's the signature of strstr? Your example really boils down to proving strstr is safe.

The problem is, strstr isn't safe by itself, it's only safe in certain contexts.  You can't mark it as @trusted either because it has the potential to be unsafe.  I think if safe D heap-allocates when it passes a local address into an unprovable function such as strstr, that's fine with me.

So the signature of strstr has to be unmarked (no @safe or @trusted).

> You're implying that the return of buf from strstr is unsafe. Indeed, my intentionally short post didn't discuss returning from functions. Ignoring that for a moment, surely you'd agree the following is safe:
>
> char[] foo(){
>     char[100] buf;
>     copystringintobuf(buf, "hi");
>     return buf[0..2].dup;
> }
>
> As far as return types, there are two subtle issues:
> 1. Returned input argument must preserve the scope requirements of the caller. A similar problem as return variables and const annotation.
> 2. Unlike const annotations, there is more than three states for scope, it's simply a measure of how deep/shallowvariables can be in the stack.

Yes, but I think such an annotation system is unworkable.  I'd rather see the compiler annotate into an intermediate file.  Even with those, you would be hard pressed to be able to prove all cases when the scope depth depends on runtime values.  That would require runtime checks.  I think escape analysis is a worthy goal, but very hard to implement.  Just allocating when you can't prove anything is a decent solution.

-Steve