www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - new DIP38: Safe references and rvalue references without runtime

reply Timothee Cour <thelastmammoth gmail.com> writes:
Abstract

In short, the compiler internally annotates ref-return functions with
ref(i1,...,iN) indicating that the function may return argument j
(j=i1...iN) by reference (possibly via field accesses), where j is
also a ref input argument. This list can be empty, and if the function
is a method or internal function, argument 0 refers to implicit 'this'
parameter. These annotations are used to validate/invalidate ref
return functions that call such a ref return function. These
annotations are also written in the automatically generated di
interface files.

See the DIP38 for more details and examples.
May 06 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 06 May 2013 14:52:23 -0400, Timothee Cour  
<thelastmammoth gmail.com> wrote:

 Abstract

 In short, the compiler internally annotates ref-return functions with
 ref(i1,...,iN) indicating that the function may return argument j
 (j=i1...iN) by reference (possibly via field accesses), where j is
 also a ref input argument. This list can be empty, and if the function
 is a method or internal function, argument 0 refers to implicit 'this'
 parameter. These annotations are used to validate/invalidate ref
 return functions that call such a ref return function. These
 annotations are also written in the automatically generated di
 interface files.

 See the DIP38 for more details and examples.

Link: http://wiki.dlang.org/DIP38 In order for this to work, the compiler must mangle according to ref specification. Otherwise, a incorrectly synchronized .di file might link code that should otherwise be rejected. I think this DIP might be too complex for acceptance. My opinion is we should try the runtime check thing. I think there will be very few cases where it is triggered. -Steve
May 06 2013
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/6/13 2:52 PM, Timothee Cour wrote:
 Abstract

 In short, the compiler internally annotates ref-return functions with
 ref(i1,...,iN) indicating that the function may return argument j
 (j=i1...iN) by reference (possibly via field accesses), where j is
 also a ref input argument. This list can be empty, and if the function
 is a method or internal function, argument 0 refers to implicit 'this'
 parameter. These annotations are used to validate/invalidate ref
 return functions that call such a ref return function. These
 annotations are also written in the automatically generated di
 interface files.

 See the DIP38 for more details and examples.

Knee-jerk reaction: this or any scheme based on internal (non-explicit) annotation for functions without that triggering inter-procedural analysis. The signature of a function should be everything the compiler can use as a basis in analysis. Andrei
May 06 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/6/13 3:03 PM, Andrei Alexandrescu wrote:
 On 5/6/13 2:52 PM, Timothee Cour wrote:
 Abstract

 In short, the compiler internally annotates ref-return functions with
 ref(i1,...,iN) indicating that the function may return argument j
 (j=i1...iN) by reference (possibly via field accesses), where j is
 also a ref input argument. This list can be empty, and if the function
 is a method or internal function, argument 0 refers to implicit 'this'
 parameter. These annotations are used to validate/invalidate ref
 return functions that call such a ref return function. These
 annotations are also written in the automatically generated di
 interface files.

 See the DIP38 for more details and examples.

Knee-jerk reaction: this or any scheme based on internal (non-explicit) annotation for functions without that triggering inter-procedural analysis.

Awfully put. I meant: this or any scheme based on internal (non-explicit) annotation for functions cannot work without triggering inter-procedural analysis. (I haven't read the DIP yet.) Andrei
May 06 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/6/13 6:41 PM, Timothee Cour wrote:
 Awfully put. I meant: this or any scheme based on internal (non-explicit)
 annotation for functions cannot work without triggering inter-procedural
 analysis. (I haven't read the DIP yet.)

The proposed scheme doesn't require any inter-procedural analysis. Each function is summarized by a label indicating its ref dependencies, and a label propagation algorithm is used to label each function.

BAM! Interprocedural analysis. Doesn't matter what name you invent for it. It's weird - you think you're in good shape, walking down the street, and suddenly you're in interprocedural analysis zone. Andrei
May 06 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/6/13 10:56 PM, Timothee Cour wrote:
 BAM! Interprocedural analysis. Doesn't matter what name you invent for it.
 It's weird - you think you're in good shape, walking down the street, and
 suddenly you're in interprocedural analysis zone.

ok, call it interprocedural analysis, but what would be your arguments against it, assuming:

I have no arguments against it other than the usual cautions about interprocedural analysis. The point here is to acknowledge the risks and liabilities. Andrei
May 06 2013
prev sibling next sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 Awfully put. I meant: this or any scheme based on internal (non-explicit)
 annotation for functions cannot work without triggering inter-procedural
 analysis. (I haven't read the DIP yet.)

The proposed scheme doesn't require any inter-procedural analysis. Each function is summarized by a label indicating its ref dependencies, and a label propagation algorithm is used to label each function. The only tricky case is the (arguably rare) case of mutually recursive ref return functions (corresponding to loops in the graph), for which we can fall back to the runtime check, but for which I also believe we can have a simple compile time solution with a bit more care. I have updated the algorithmic details in the DIP.
May 06 2013
prev sibling next sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 BAM! Interprocedural analysis. Doesn't matter what name you invent for it.
 It's weird - you think you're in good shape, walking down the street, and
 suddenly you're in interprocedural analysis zone.

ok, call it interprocedural analysis, but what would be your arguments against it, assuming: A) I can convince (with code) that the propagation algorithm is simple to implement and has negligible compile time overhead B) it is safer than proposed approach in release builds (because unittests in debug builds might not catch all such bugs, for example things like min(ref int x, ref int y) which might be correct in some code paths but not all) C) it is faster in debug builds because no runtime checks
May 06 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/6/2013 11:52 AM, Timothee Cour wrote:
 See the DIP38 for more details and examples.

Handy link: http://wiki.dlang.org/DIP38
May 06 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/6/2013 11:52 AM, Timothee Cour wrote:
 Abstract

 In short, the compiler internally annotates ref-return functions with
 ref(i1,...,iN) indicating that the function may return argument j
 (j=i1...iN) by reference (possibly via field accesses), where j is
 also a ref input argument. This list can be empty, and if the function
 is a method or internal function, argument 0 refers to implicit 'this'
 parameter. These annotations are used to validate/invalidate ref
 return functions that call such a ref return function. These
 annotations are also written in the automatically generated di
 interface files.

 See the DIP38 for more details and examples.

It requires interprocedural analysis. This is possible for the same functions (such as template functions) that can infer pure/nothrow/ safe, but it cannot be done for ordinary functions.
May 06 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/6/13 11:44 PM, Timothee Cour wrote:
 It requires interprocedural analysis. This is possible for the same
 functions (such as template functions) that can infer pure/nothrow/ safe,
 but it cannot be done for ordinary functions.

Can you please provide me a simple example for which the algorithm proposed in the DIP38 will fail, and that does not involve cycles (as described in the DIP) ?

No. That's not the problem. It may as well work. When typechecking a function, ALL you have is: 1. the body of that function 2. the signatures of all other functions. NOT adorned with extra info, NO bodies, NO nothing. You need to make-do with that. Everything else explodes into interprocedural analysis. It's as cut and dried as it gets. Andrei
May 06 2013
prev sibling next sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 It requires interprocedural analysis. This is possible for the same
 functions (such as template functions) that can infer pure/nothrow/ safe,
 but it cannot be done for ordinary functions.

Can you please provide me a simple example for which the algorithm proposed in the DIP38 will fail, and that does not involve cycles (as described in the DIP) ?
May 06 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 6 May 2013 at 18:52:36 UTC, Timothee Cour wrote:
 Abstract

 In short, the compiler internally annotates ref-return 
 functions with
 ref(i1,...,iN) indicating that the function may return argument 
 j
 (j=i1...iN) by reference (possibly via field accesses), where j 
 is
 also a ref input argument. This list can be empty, and if the 
 function
 is a method or internal function, argument 0 refers to implicit 
 'this'
 parameter. These annotations are used to validate/invalidate ref
 return functions that call such a ref return function. These
 annotations are also written in the automatically generated di
 interface files.

 See the DIP38 for more details and examples.

I agree on Andrei on that one. It breaks separate compilation model.
May 06 2013
prev sibling next sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
Ok, I have updated and simplified the DIP38, please take a look. In
the proposed 'manual' scheme A, the user annotates each ref argument of a
ref-return function with either inref or outref (let's postpone the
discussion of what exactly those keywords should be and focus on the
logic instead; see bottom of email for a possibility). In proposed
scheme B, the inref/outref are instead
automatically infered. Let's focus on scheme A to avoid doing
interprocedural analysis.

Then all we need is to check whether the program typechecks under the
following type conversion rules:

global => outref //global: gc-allocated, static, etc.
output of ref-return function call => outref
outref 'dot' field => outref // field access
local => inref
global => inref
outref => inref
temporary => inref

where A=>B means that a variable of type A can be used in a context
where type B is expected.

see DIP38 for details and examples

I also would argue that it makes sense for the user to write
inref/outref instead of ref, indicating explicit intent on whether or
not to escape a ref argument. This is much simpler than rust's named
lifetime annotations as far as I understand, since it's just a binary
choice.

To avoid breaking code, we can assume that 'ref' means 'outref' and
'scope ref' means 'inref'.
Note, that this isn't the same as the rejected proposal DIP36, which
did not address escaping issues (it only dealt with non ref return
functions).

Example1:
ref T fooa(ref T t) { return t; }
ref T bar() { T t; return fooa(t); }
currently might compile, but has undefined behavior. Under the new
rules (with ref meaning outref), it would not compile because of the
illegal conversion local => outref when attempting to call fooa(t).

Example2:
ref T fooa(inref T t) { static T t2; return t2; }
ref T bar() { T t; return fooa(t); }
here this compiles because we've annotated the input argument to fooa
as inref, as foo returns a global.
May 06 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 7 May 2013 at 06:28:54 UTC, Timothee Cour wrote:
 Then all we need is to check whether the program typechecks 
 under the
 following type conversion rules:

 global => outref //global: gc-allocated, static, etc.
 output of ref-return function call => outref
 outref 'dot' field => outref // field access
 local => inref
 global => inref
 outref => inref
 temporary => inref

Redundant rules should usually be avoided. For isntance, global => inref is pointless as global => outref => inref does it.
 Example1:
 ref T fooa(ref T t) { return t; }
 ref T bar() { T t; return fooa(t); }
 currently might compile, but has undefined behavior. Under the 
 new
 rules (with ref meaning outref), it would not compile because 
 of the
 illegal conversion local => outref when attempting to call 
 fooa(t).

Prevent valid code like T t2 = fooa(fooa(t)); in bar.
May 06 2013
prev sibling next sibling parent "Namespace" <rswhite4 googlemail.com> writes:
DIP 36 also forgot to mention which lifetime a temporary has, 
relating to the rvalue references.
And I do not see it even at your DIP.
And AFAIK 'scope ref' was *generally* rejected. 'auto ref' should 
/ will eventually be the answer someday.
May 06 2013
prev sibling next sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 Prevent valid code like T t2 = fooa(fooa(t)); in bar.

Thanks for the counter-example; I think I can still save the proposal with the following conversion rules: global => outref //global: gc-allocated, static, etc. outref 'dot' field => outref // field access ref function(args) where each outref arg of args is an outref expression => outref ref function(args) where at least one outref arg of args is not an outref expression => local inref => local return outref => outref return local => local // compile error if this is a ref return function (I've also updated the DIP38). Can you break these rules?
May 07 2013
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 07 May 2013 00:45:56 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 5/6/13 11:44 PM, Timothee Cour wrote:
 It requires interprocedural analysis. This is possible for the same
 functions (such as template functions) that can infer  
 pure/nothrow/ safe,
 but it cannot be done for ordinary functions.

Can you please provide me a simple example for which the algorithm proposed in the DIP38 will fail, and that does not involve cycles (as described in the DIP) ?

No. That's not the problem. It may as well work. When typechecking a function, ALL you have is: 1. the body of that function 2. the signatures of all other functions. NOT adorned with extra info, NO bodies, NO nothing.

I think the DIP fairly clearly says that either it has the function bodies, or the compiler-generated .di files WITH the extra info added. -Steve
May 07 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, May 06, 2013 23:28:40 Timothee Cour wrote:
 Ok, I have updated and simplified the DIP38, please take a look. In
 the proposed 'manual' scheme A, the user annotates each ref argument of a
 ref-return function with either inref or outref (let's postpone the
 discussion of what exactly those keywords should be and focus on the
 logic instead; see bottom of email for a possibility). In proposed
 scheme B, the inref/outref are instead
 automatically infered. Let's focus on scheme A to avoid doing
 interprocedural analysis.

I confess that my gut reaction to all of this is that it's just plain simpler to do the runtime check. It won't be needed often and is trivial to disable if you don't want it. And it requires no annotations whatsoever. We're already seriously pushing it with the sheer number of annotations that we have, so I'm very much inclined to argue against adding new ones if we don't really need them. - Jonathan M Davis
May 07 2013
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 07 May 2013 15:20:43 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Monday, May 06, 2013 23:28:40 Timothee Cour wrote:
 Ok, I have updated and simplified the DIP38, please take a look. In
 the proposed 'manual' scheme A, the user annotates each ref argument of  
 a
 ref-return function with either inref or outref (let's postpone the
 discussion of what exactly those keywords should be and focus on the
 logic instead; see bottom of email for a possibility). In proposed
 scheme B, the inref/outref are instead
 automatically infered. Let's focus on scheme A to avoid doing
 interprocedural analysis.

I confess that my gut reaction to all of this is that it's just plain simpler to do the runtime check. It won't be needed often and is trivial to disable if you don't want it. And it requires no annotations whatsoever. We're already seriously pushing it with the sheer number of annotations that we have, so I'm very much inclined to argue against adding new ones if we don't really need them.

While I agree here, and there is the cognitive load of understanding the attributes to take into account, I like the proposed mechanism to propagate attributes to the .di file automatically for no-body functions. That in itself would enable attribute inference, as long as developers of closed-source libraries agreed to use that mechanism. -Steve
May 07 2013