Richard (Rikki) Andrew Cattermole 
| I've done an almost complete rewrite, I expect this to be close to the final version:
- Globals only need to be loaded from, after that they may become an owner
- I changed how ``scope`` works, it is no longer a flag, its instead a relationship strength, establishing a relationship strength is what changed the majority of the document.
- New attribute ``@move`` inferred, allows for functions like swap and move to be modelled without you needing to add said attribute (DIP1000 doesn't do any of this).
- Acknowledgement that DIP1000 attributes can live side by side these ones, meaning the migration from DIP1000 would be a smooth one.
Current: https://gist.github.com/rikkimax/0c1de705bf6d9dbc1869d60baee0fa81/5dba16b3b1fbe250b31ae237dda2ffc7b66f9399
As I believe this is more less complete, I'll include a copy here.
--------------------------------------------------------------------------------------------------------------
# Escape Analysis
| Field | Value |
|-----------------|-----------------------------------------------------------------|
| DIP: | (number/id -- assigned by DIP Manager) |
| Author: | Richard (Rikki) Andrew Cattermole <firstname@lastname.co.nz> |
| Implementation: | (links to implementation PR if any) |
| Status: | Draft |
## Abstract
The movement of pointers within a program graph easily escapes known points that own that memory within the call stack of a given thread. This logical error can result in program termination or undetected corruption of the program state. This proposal is a new attempt at preventing this corruption within the ``@safe`` code.
## Contents
* [Rationale](#rationale)
* [Prior Work](#prior-work)
* [Description](#description)
* [Breaking Changes and Deprecations](#breaking-changes-and-deprecations)
* [Reference](#reference)
* [Copyright & License](#copyright--license)
* [Reviews](#reviews)
## Rationale
In a review of the existing escape analysis solution implemented in D's reference compiler DIP1000, there is one major limitation of what it models and assumption growth to facilitate functionality.
The implementation of DIP1000 models a single output variable per function, this is the return value or if ``void`` the first parameter (could be the ``this`` pointer). In practice functions typically have more than one output, this includes mutable pointers in, ``ref`` and ``out`` function parameters.
```d
int* /* output */ func();
struct S {
int* /* output */ method1();
void method2() /* output */;
}
```
The relationship between parameters is modelled using the ``return ref`` and ``return scope`` attributes. These communicate to the compiler the varying input and how it relates to the output for that parameter.
Needing two different attributes to determine the relationship status between parameters has been highly incommunicable to experienced programmers.
Due to it not being able to model multiple outputs, a lot of typical D code cannot be safely represented using DIP1000. The design does not protect you from extending past the modelled subset of the language.
To resolve both of these core issues in the existing design, an escape set must be modelled per parameter. While this resolves the callee's side, it does not protect the caller from misusing the callee. The design DIP1000 attempts to solve this by modelling the relationship between parameters using the two different attributes.
Another solution to this problem is to utilize the information provided by escapes and inverse it, given an output and given the inputs that form it, protect the inputs so that nothing can invalidate the output. This resulted in the proposal that was ``@live``, an opt-in analysis that does not communicate to either the callee or caller any guarantees cross-function, making it functionally irrelevant to the guarantees of DIP1000.
An opt-in solution to ownership does not allow for reference counting to occur safely. To safely do this, the referenced counted owner must be pinned and made effectively read-only so that both a reference to it and the borrowed resource may be passed around. This was a [blocker](https://forum.dlang.org/post/v0eu64$23bj$1@digitalmars.com) determined by Walter and Timon for adding reference counting to the language.
Furthermore without the entry point to escape analysis having analysis associated with it, there is no differentiation of what can constitute of a safe to borrow from source and what can't be. An example of this is with a global, in the case of a variable thread local storage, it is possible in fully ``@safe`` code with DIP1000 turned on to cause a segfault.
```d
import std;
int* tlsGlobal;
@safe:
void main() {
tlsGlobal = new int(2);
assert(*tlsGlobal == 2);
toCall();
assert(*tlsGlobal == 2); // Segfault
}
void toCall() {
tlsGlobal = null;
}
```
## Prior Work
Escape analysis as a subject matter is primarily an [analysis of graphs](https://dl.acm.org/doi/10.1145/320385.320400). How they are mutated and who owns them at what places. Modelling this can be an expensive set of operations in the form of data flow analysis. For sufficient and best experience, a full program analysis is needed with a full graph of manipulation and logic therein analysed.
Native programming languages do not align themselves to full program analysis, due to the separate compilation model. D is a native programming language that uses this model almost exclusively. For this reason, it cannot use a full program analysis and full program graph analysis for modelling escaping. Instead, a flattened view of the graph must be representable inside a function signature.
At the time of this proposal, a solution for escape analysis has been implemented in the D reference compiler that is commonly referred to by its DIP number, DIP1000. This does not cover memory ownership guarantees, instead ``@live`` as an opt-in attribute enables some localized to the given function guarantees.
In Rust ownership is a [transfer based system](https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html), so that only one variable has any ownership of memory. In contrast to D, where this is modelled and attempting to enforce this would not match how garbage collected memory would be used. Further [guarantees](https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html) are given, in that when a borrow occurs from an owner, only one mutable borrow is allowed in a given scope. This complements the ownership transfer system as it guarantees nobody else has the potential for aliasing.
## Description
This proposal introduces escape analysis, owner escape analysis along with a way to know if a variable associated with an argument has changed its value post function call.
What escape analysis and its complement owner escape analysis does, is it protects against invalidation of memory ownership whilst one or more borrows exist.
The grammar changes for the new function are described here, removal of DIP1000 and ``@live`` are done in its own heading ``Removal of Existing Language Elements``.
```diff
AtAttribute:
+ @ EscapeAttribute
+ @ move
ParameterAttributes:
+ @ EscapeAttribute
+ EscapeAttribute:
+ escape ( Identifiers )
+ escape ( )
+ escape
FuncAttr:
+ FuncAttrMove
+ FuncAttrMove:
+ No
```
The semantic analysis for both analysis, is done at the same time as they are guarantees provided in complement of each other and do not exist in isolation. A switch should be provided to disable this analysis should a use case is required to not perform it in the form of ``--disable-memorysafety``. If it is not set, it will be enabled for a given edition and above by default. For any edition below this will include the inferring of ``@escape`` and ``@move`` attribute, however no errors will be generated for either attribute.
There is some potential for the escape set on a parameter to be explosive in nature for mangling. At this time no specific mangling scheme is suggested, but it is allowed in this proposal for one to be implemented.
### Relationships
An expression is said to have a set of relationships between its inputs and outputs, with some kind of transformation applied to the inputs to get the outputs. This is described using the formula ``T(inputs...) = (outputs...)``.
A function prototype, or function pointer declares this relationship, without providing the transformation function. An example of a transformation in the form of an identity function is given:
```d
int* identity(/* has relationship to return */ int* input) => input;
```
The return value of the ``identity`` function is the output and has a relationship to the ``input`` parameter.
Each relationship of an input to its outputs can be described as having a strength. These strengths are:
- No relationship
- Weak, comes from input and influences output
- Strong, requires the input to be valid for the output to be valid
For example, to get a strong relationship you can take a pointer to stack memory:
```d
int input;
/*has a strong relationship*/ int* output = &var;
```
In this example, the variable ``input`` must outlive the variable ``output``, if you don't you will get stack corruption.
Another way you can get a strong relationship is to assign a copy of the value that is stored in an already strong relationship variable.
```d
/*has a strong relationship*/ int* input = ...;
int* output = var; // has a strong relationship
```
The way to explicitly establish the link between a variable and its initializer as strong is to annotate it with ``scope``.
```d
scope int* input = ...;
int* output = var; // has a strong relationship
```
These three behaviors of establishing a relationship between two variables also applies when a containing type is in play:
```d
struct Input {
int* ptr;
int field;
}
Input input1 = ...;
int* output1 = &input1.field; // has a strong relationship between `output1` and `input1`
scope Input input2 = ...;
int* output2 = input2.ptr; // has a strong relationship between `output2` and `input2`
```
The default relationship of a function's outputs to its inputs is weak, unless the argument for a given input has a strong relationship. In the following example the ``input`` variable has a strong relationship to the stack. So when it gets the output from the ``identity`` function call it has a strong relationship to its input too.
```d
scope input = new int;
int* output = identity(input);
// `output` variable has a strong relationship to `input` variable
```
A way to require that a given input has a strong relationship to its outputs is by marking a function parameter as scope.
```d
int* strongIdentity(/* has relationship to return */ scope int* input) => input;
```
Now you can take an input that does not have a strong relationship, and require the output has a strong relationship to it!
```d
int* input = new int;
int* output = strongIdentity(input);
// `output` variable has a strong relationship to `input` variable
```
A weak relationship between an input and output, does not limit the output. It only establishes that there is an relationship to be had. This can be quite useful to composed types like tuples and static arrays:
```d
int* transformation(int* input) {
int*[2] array;
array[0] = input; // `array` has a weak relationship to `input`
array[1] = new int; // GC allocation has no relationships without a constructor call or initializer to form one
return array[0];
}
```
In the above example, the output value of the function will not be constrained by the variable ``array``. But the weak relationship from the ``array`` variable to ``input`` parameter, will be inherited by the return value, giving the following prototype:
```d
int* transformation(/* has relationship to return */ int* input);
```
Setting up a relationship within a function body is one thing, but to do it within a function signature? That is much harder. In the following example, a weak relationship is established where an input pointer is stored inside an output static array.
```d
void assignElement(ref int*[2] output, /* has a relationship to output */ int* input) {
output[0] = input;
output[1] = new int;
}
```
The previous examples in this heading used a raw pointer ``int*`` to establish relationships, the full list of types that affect the formation of relationships are:
- Slices: ``T[]``
- Raw pointers: ``T*``
- Associative arrays: ``T[U]``
- Pointer-containing fields or elements:
- Structs
- Unions
- Static arrays
- Tuples
- Any by-ref input parameter or variable will have an implicitly strong relationship to its output if it is also by-ref.
Other types, that behave as a value type like ``int`` are unaffected and do not establish a relationship. This means that they may be interacted with without establishing a relationship.
### Escape set
Previously this proposal has limited the terminology to establishing a relationship between a given input to its outputs. In this heading the method for describing this relationship in code is presented.
A new attribute is provided, ``@escape(...)``, within the brackets an escape set is provided using the following identifiers as elements within it:
- Nothing
- ``return``
- ``this``, also applies to the context pointer of a delegate.
- ``__unknown``, for exceptions, and globals.
- ``__parameters``, for all parameters, except the current one.
- Any function parameter names.
This attribute may be placed on function parameters and on the function which is represents the ``this`` pointer.
When the attribute is missing its escape set, it defaults the escape set to ``@escape(return, this, __unknown, __parameters)``. When the annotation is missing, this will indicate that it is to be inferred.
```d
alias D = T delegate(@escape U input1, @escape(return) V input2) @escape(return);
T freeFunction(@escape U input1, @escape(return) V input2);
class C {
T method(@escape U input1, @escape(return) V input2) @escape(return);
}
```
The escape set only applies to types that are pointers. Non-pointers do not have an escape set, and therefore no ``@escape`` attribute. Function parameters that are non-pointers will have their attribute removed if it is specified. The ``this`` pointer is always a pointer type, even for structs.
For easier reading the empty escape set may be elided for variables that are marked ``scope``. A non-empty escape set must remain on the variable and cannot be elided.
```d
void doSomething(@escape() scope int* input);
```
Will become:
```d
void doSomething(scope int* input);
```
When a function pointer or delegate does not have an annotation for an escape set, it is assumed to be the empty set. This is a safe assumption thanks to the type system enforcing it.
```d
alias F = int* function(int*);
int* identity(@escape(return) int* input){
return input;
}
F func = &identity; // Error: Variable `func` has type `int* function(int*)` and cannot be assigned `int* function(@escape(return) int*)`
```
Functions that are ``@trusted`` have their function signatures inferred for escapes, but will not error within the body or when the body does not match the signature. For ``@safe`` functions these are inferred but will error within the body and when the signature does not match the body. Lastly ``@system`` functions will not be analysed for escapes and any annotation of escapes upon its signature will be ignored.
The compiler has no way to assume what an escape set contains for a function declaration without a body. To verify it there is an implicit assumption that the linker will catch it by comparing symbol names with the help of mangling. To prevent accidental assumptions creeping into ``@safe`` code, any function without a body that is not fully annotated for the escape sets, will be downgraded to ``@system``. The following function declaration would be treated as if it wasn't annotated as ``@safe``.
```d
int* someFunction(int*, @escape() int*) @safe;
```
But this will be ``@safe``:
```d
int* someFunction(scope int*, @escape() int*) @safe;
```
Not all ABI's support name mangling of escape sets. By taking the responsibility of escape annotation requirement off the linker, this guarantees the compiler is able to provide stronger guarantees for memory safety analysis without the linker providing a backdoor using innocuous looking code.
When ``scope`` is placed upon a variable, it requires that when a variable is converged to not escape into unknown locations. This means that ``__unknown`` is not allowed to appear in the escape set. This also applies when a weak relationship parameter is upgraded to strong by the argument.
```d
void func1(@escape(__unknown) scope int* ptr); // Error the parameter `ptr` cannot have an escape set that includes `__unknown` and be marked as having a strong relationship `scope`
void func2(@escape(__unknown) int* ptr);
scope int* ptr;
func2(ptr); // Error variable `ptr` has a strong relation and cannot be escaped out through a `__unknown` parameter
```
Overriden methods in classes must have an escape set per parameter that is less than or equal to the parent method's set.
```d
class Parent {
int* method() @escape(return);
}
class Child : Parent {
override int* method() @escape(return, __unknown); // Error: the escape set for the `this` pointer on `method` must be equal or lesser than the parent which is `return` not `return, __unknown`
}
```
#### An Input Changed its Known Value
Sometimes an argument will have its value changed from the input. This is quite important for by-ref parameters who may have its value being tracked. To indicate to the compiler that it should not consider the value prior to a call is the same as the one after, the attribute ``@move`` on a parameter will indicate it will have changed. Common functions that demonstrate this behavior are ``swap`` and ``move``.
```d
T move(T)(@move @escape(return) T input) {
return input;
}
```
At most one escape in the escape set of a parameter, to an output that has only one input may be used to allow the compiler to track movement of a given value between function calls.
```d
void swap(T)(@move @escape(input2) ref T input1,
@move @escape(input1) ref T input2) {
T temp = input1;
input1 = input2;
input2 = temp;
}
int* a, b;
swap(a, b);
// Compiler can see that b is in a
// Compiler can see that a is in b
```
All ``out`` parameters will have ``@move`` applied to it automatically and need not be programmer applied.
If the ``@move`` attribute is applied to a parameter that is not by-ref, templated or the parameter type does not have move constructors it is an error.
As an attribute ``@move`` may be inferred if the compiler can see that the input was changed for a given parameter at the end of the called function's body.
```d
struct Unique {
int* ptr;
this(/*@move*/ ref Unique other) {
this.ptr = other.ptr;
other = Unique.init; // the input into `other` was changed
}
}
```
#### Analysis
The goal of escape analysis, is to have an accurate accounting of where inputs go to their outputs and how to converge it between scopes. It provides protection from false assumptions on lifetimes creeping into ``@safe`` code.
An example of two scopes, whereupon assignment resets the escape set of an inner variable:
```d
int* outer;
{
int* inner = ...;
outer = inner;
// @escape(outer) inner
// Converge `outer` with any owners of `inner` lifetimes
inner = ...;
// @escape() inner
}
```
When converging on multiple sets instead of taking the minimum set and erroring, the analysis will take the maximum set of all the scopes:
```d
int* func(int* input) {
if (input is null) {
return new int;
// @escape() input
} else {
return input;
// @escape(return) input
}
// @escape(return) input
}
```
Elements in an array, fields in a class/struct/union are conflated with the variable that stores them in. Supporting awareness and the differentiation of each of these cases is not included in this proposal but a subset coudl be done.
```d
struct S {
int* field;
}
void handle(int* ptr) {
S s;
s.field = ptr;
// @escape(s) ptr
}
```
The point of convergence matters for lifetime analysis. It occurs like regular function destructor cleanup for a given scope. It happens in reverse order of the declarations. This has consequences, it allows a variable that has a strong relationship, to grow its escape set during its scope, but be a lot smaller at the end.
```d
struct S {
int* field;
}
int* acquire(ref S s) @safe {
return s.field;
}
void caller() @safe {
int x = 2;
S s = S(&x);
*acquire(s) = 3;
}
```
Is equivalent to:
```d
struct S {
int* field;
this(@escape(this) int* field) @safe {
this.field = field;
}
}
int* acquire(@escape(return) ref S s) @safe {
return s.field;
}
void caller() @safe {
int x = 2;
scope xPtr = &x;
// @escape(xPtr) x, escape set cannot grow
S s = S(xPtr);
// @escape(s) xPtr
int* fooReturn = acquire(s);
// @escape(fooReturn) s
*fooReturn = 3;
__cleanup(fooReturn); // Cleanup code from compiler such as destructors get injected here
// @escape() s
__cleanup(s); // Cleanup code from compiler such as destructors get injected here
// @escape() xPtr
__cleanup(xPtr); // Cleanup code from compiler such as destructors get injected here
// @escape() x
__cleanup(x); // Cleanup code from compiler such as destructors get injected here
// x escape set is empty, therefore ok
}
```
### Owner Escape Analysis
Seeing what variable contributes to another (or becomes), is one thing, but that does not provide guarantees in of itself. For guarantees to be made the relationship between variables must be made inversely. This inverse relationship describes an output variable as being a borrow to one or more owner input variables.
To establish a borrow, a variable must have one or more relationships to it that are strong.
```d
int owner;
int* borrowed = &owner;
// `borrowed` has a strong relationship to `owner`
```
Function calls:
```d
int* identity(/*@escape(return)*/ int* input) {
return input;
}
int owner;
int* borrowed = identity(&owner); // Due to `&owner` `borrowed` has a strong relationship to `owner`
```
Borrowed memory is only ever valid, as long as the owners are not mutated. Mutation of the owners could unmap the borrowed memory, or change it in such a way that the program becomes corrupted. When a borrow is seen, the compiler protects the owner from mutation by requiring it to be "effectively const" as long as borrows exist. It cannot be assigned to, or be passed to methods or functions mutably.
```d
struct Top {
int* field;
}
void func(ref Top owner) @safe {
int* field = owner.field;
// owner is now effectively const, it cannot be mutated
owner = Top.init; // Error: The variable `owner` has a borrow and cannot be mutated
owner.field = null; // Error: The variable `owner` has a borrow and cannot be mutated
if (field !is null) {
writeln(*field);
*field = 2; // ok, fully mutable
}
}
```
When converging between multiple scopes, the borrowed variables must have the same value in it.
```d
int owner;
int* borrowed;
if (random() > 0.5) {
borrowed = &owner;
} else {
}
// Error: Variable `borrowed` has two different values in it, it can be owned by `owner` and be null
```
Side effects from method calls must be prevented, otherwise it will be possible to invalidate a borrow unknowingly. An existing language element for this is for checking against mutability, whereby mutable is disallowed but non-mutable allowed.
```d
struct S {
int field;
@safe:
bool isNull() const {
return false;
}
void makeNull() {
}
}
S s;
int* field = &s.field;
writeln(s.isNull); // ok
s.makeNull(); // Error: Variable `s` has a borrow and may not be mutated by calling `makeNull`.
```
The attribute ``@move`` indicates that a function call will mutate the input, and therefore if there are borrows from that variable to error.
```d
void someConsumer(@move scope ref int* input);
int* owner = ...;
int** borrowed = &owner;
someConsumer(owner); // Error: Variable `owner` has a borrow and cannot be moved into the parameter as it would invalidate the borrows
```
#### Global Variables
Not all variables can be tracked throughout a program's lifecycle. Global variables including those in thread local storage, can appear in any point in the call stack multiple times. Pinning of specific values into existance cannot occur for a global for this reason. It can be changed out from under you with no way to prevent it in ``@safe`` code.
Loading a value that is a pointer (including structs with pointer fields), into another will apply a flag onto that variable to say it contains global memory. This corresponds with the ``__unknown`` relationship argument.
```d
int* global;
void func() {
int* ptr = global;
// is a global `ptr`
}
```
This is useful information to have, as it informs any memory that tries to contribute to it, that it will be escaped out through ``__unknown`` lifetime.
```d
int** global;
void func() {
int** globalPtr = global;
// is a global `globalPtr`
int value;
int* ptr = &value;
// Variable `ptr` is owned by the stack
*globalPtr = ptr; // Error: variable `ptr` which has a shorter lifetime cannot be placed into globally accessible memory in `globalPtr`
}
```
It isn't limited to a single call frame, it can protect against cross-function scopes as well.
```d
int** global;
void caller() {
int** globalPtr = global;
// is a global `globalPtr`
int value;
int* ptr = &value;
// Variable `ptr` is owned by the stack
called(globalPtr, ptr); // Error: Variable `ptr` which is owned by the stack would escape into a longer lifetime memory that is globally accessible `globalPtr`
}
void called(@escape() int** globalPtr, @escape(globalPtr) int* ptr) {
*globalPtr = ptr;
}
```
### Removal of Existing Language Elements
The language design elements that are being removed are DIP1000 and ``@live``. Together these attempted to do this proposal but in a non-integrated way that has shown minimal adoption.
```diff
Attribute:
- return
AtAttribute:
- @ live
FuncAttr:
- FuncAttrReturn
- FuncAttrLive
- FuncAttrReturn:
- Nj
- FuncAttrLive:
- Nm
```
No timeline is specified for removal.
## Breaking Changes and Deprecations
DIP1000 will not be able to be turned on at the same time as this proposal.
Any syntax specific (such as ``return`` attribute) to DIP1000 will break.
Any new semantic analysis would only cause errors to be applied to a new edition and would not affect the base D2 language.
During the transition period from DIP1000 to this proposal, the attributes from each proposal that is not active do not contribute to mangling. This enables attributes from each proposal to live side by side to keep a code base compiling.
## Reference
- [Shape Analysis](https://en.wikipedia.org/wiki/Shape_analysis_(program_analysis)) (type state & memory escapes)
- [@system variables DIP](https://github.com/dlang/DIPs/blob/master/DIPs/accepted/DIP1035.md)
- [# Compositional pointer and escape analysis for Java programs](https://dl.acm.org/doi/10.1145/320385.320400)
- [4.1. What is Ownership?](https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html)
- [4.2. References and Borrowing](https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html)
## Copyright & License
Copyright (c) 2024 by the D Language Foundation
Licensed under [Creative Commons Zero 1.0](https://creativecommons.org/publicdomain/zero/1.0/legalcode.txt)
## History
The DIP Manager will supplement this section with links to forum discussions and a summary of the formal assessment.
|
Permalink
Reply
