On 12/08/2024 10:02 PM, Quirin Schroll wrote:
>>>> > No data flow analysis is proposed. Null checking is local > and
>>>> done by tracking ? and ! by the type system.
>>>>
>>>> DFA is only required if you want the type state to change as the function is interpreted. So that's fine. That is a me thing to figure out.
>>>
>>> If I understand correctly, by “type state” you means something like value range propagation. It basically *is* value range propagation, however the ranges in question are `null` and all non-null values. You don’t suggest `typeof` type of a variable or expression changes, correct? (I think that would be very weird.)
>>
>> No, I meant type state.
>>
>> https://en.wikipedia.org/wiki/Typestate_analysis
>>
>> unreachable < reachable < initialized < default-initialized < non-null < user
> 
> I didn’t read the Wikipedia article in detail, but it contains no “null,” so I’m wondering how it’s related. A variable of non-nullable type must be initialized. If we’re talking `@system` code, fine, it need not be, it could even be void initialized. IIUC, typestate analysis could be used to make void initialization `@safe` by proving that a void initialized value has definitely been initialized whenever it’s read (i.e. no uninitialized read).
> 
> IIUC, what you’re suggesting is allowing variables of non-null type to be initialized by `null`, but that reading one requires them to be initialized.

No.

Initialized, just means it has been initialized. The value, has no guarantees beyond this.

It may be read, it may be mutated.

A non-null type state, means that it has been initialized AND its value isn't the sentinel value null.

If it is non-null it may be dereferenced. An initialized pointer may not be dereferenced as it is lower than non-null.

>>>> However, you do not need to annotate function body variables with this approach.
>>>>
>>>> Look at the initializer of a function variable declaration, it'll tell you if it has the non-null type state.
>>>>
>>>> ```d
>>>> int* ptr1;
>>>> int* ptr2 = ptr1;
>>>> ```
>>>
>>> The only issue is, just because e.g. a pointer is initialized with something non-null (e.g. the address of a variable), that doesn’t mean some logic later won’t assign `null` to it.
>>
>> Right, that would have to be disallowed without DFA, since the type state must not change throughout a function body.
> 
> Why wouldn’t it be able to?

You need the DFA to be able to prove the guarantees in the type system hold.

Remove the ability for the type state to change, and you don't need the DFA.

>>>> However the problem which caused me some problems in the past is on tracking variables outside of a function. You cannot do it.
>>>>
>>>> Variables outside a function change type state during their lifespan. They have the full life cycle, starting at reachable, into non-null and then back to reachable. If you tried to force it to be non-null, the language would force you to have an .init value that is non-null. This is an known issue with classes already. It WILL produce logic errors that are undetectable.
>>>
>>> I don’t care much about tracking. Probably, with `if (auto) ...`, you can just rename the variable, but typed non-nullable:
>>>
>>> ```d
>>> void f(int*? p)
>>> {
>>>      if (int* q = p) ... else return;
>>>      int v = *q; // no error, q isn’t nullable, not by analysis, just by type
>>> }
>>> ```
>>
>> What matters here is that you do not need to add annotation to the type itself. It only needs to exist within the function signature. Anywhere else its useless information.
> 
> I don’t understand. To me, `Object!` and `Object?` are related but different types. You can have arrays of them, etc., how else would the information of nullableness be retained?
> 
> Maybe I need some info dump on type state analysis and what you mean exactly, because as I understand, TSA would only give you an implicit cast from `T?` to `T!` in some cases, similar to how uniqueness gives you an implicit cast from `T` to `immutable(T)` in some cases.

No, it goes in both direction.

Type state analysis is based upon a scale, that has a transfer function to go up and down it.

You start with unreachable, meaning you cannot read or mutate it. Any access is an error.

Next is reachable, you can write to it, but cannot read it. This is void initialized (uninitialized). When a variable declaration is seen this is the default prior to handling the initializer expression.

Initialized can be both read and mutated. It is the default in D. For pointers this is the sentinel value null. Aka its nullable. It must not be dereferenced.

Non-null is a pointer proven to not be the sentinel value null. It may be dereferenced as well as read/mutated.

As you increase in the scale, you get more guarantees, and therefore safety to perform otherwise potentially wrong logic.

In such analysis, with a DFA you do it as part of the variables, not the types.

```d
int* var;
// type state initialized

if (var !is null) {
	// type state non-null
} // type state min(initialized, non-null)

var = new int;
// type state non-null
```

On 13/08/2024 10:33 PM, Quirin Schroll wrote:
> On Monday, 12 August 2024 at 12:02:52 UTC, Richard (Rikki) Andrew Cattermole wrote:
>> On 12/08/2024 10:02 PM, Quirin Schroll wrote:
>>>>>> > No data flow analysis is proposed. Null checking is local
>>>>>> > > and
>>>>>> done by tracking ? and ! by the type system.
>>>>>>
>>>>>> DFA is only required if you want the type state to change as the function is interpreted. So that's fine. That is a me thing to figure out.
>>>>>
>>>>> If I understand correctly, by “type state” you means something like value range propagation. It basically *is* value range propagation, however the ranges in question are `null` and all non-null values. You don’t suggest `typeof` type of a variable or expression changes, correct? (I think that would be very weird.)
>>>>
>>>> No, I meant type state.
>>>>
>>>> https://en.wikipedia.org/wiki/Typestate_analysis
>>>>
>>>> unreachable < reachable < initialized < default-initialized < non-null < user
>>>
>>> I didn’t read the Wikipedia article in detail, but it contains no “null,” so I’m wondering how it’s related. A variable of non-nullable type must be initialized. If we’re talking `@system` code, fine, it need not be, it could even be void initialized. IIUC, typestate analysis could be used to make void initialization `@safe` by proving that a void initialized value has definitely been initialized whenever it’s read (i.e. no uninitialized read).
>>>
>>> IIUC, what you’re suggesting is allowing variables of non-null type to be initialized by `null`, but that reading one requires them to be initialized.
>>
>> No.
>>
>> Initialized, just means it has been initialized. The value, has no guarantees beyond this.
>>
>> It may be read, it may be mutated.
>>
>> A non-null type state, means that it has been initialized AND its value isn't the sentinel value null.
>>
>> If it is non-null it may be dereferenced. An initialized pointer may not be dereferenced as it is lower than non-null.
>>
>>>>>> However, you do not need to annotate function body variables with this approach.
>>>>>>
>>>>>> Look at the initializer of a function variable declaration, it'll tell you if it has the non-null type state.
>>>>>>
>>>>>> ```d
>>>>>> int* ptr1;
>>>>>> int* ptr2 = ptr1;
>>>>>> ```
>>>>>
>>>>> The only issue is, just because e.g. a pointer is initialized with something non-null (e.g. the address of a variable), that doesn’t mean some logic later won’t assign `null` to it.
>>>>
>>>> Right, that would have to be disallowed without DFA, since the type state must not change throughout a function body.
>>>
>>> Why wouldn’t it be able to?
>>
>> You need the DFA to be able to prove the guarantees in the type system hold.
>>
>> Remove the ability for the type state to change, and you don't need the DFA.
>>
>>>>>> However the problem which caused me some problems in the past is on tracking variables outside of a function. You cannot do it.
>>>>>>
>>>>>> Variables outside a function change type state during their lifespan. They have the full life cycle, starting at reachable, into non-null and then back to reachable. If you tried to force it to be non-null, the language would force you to have an .init value that is non-null. This is an known issue with classes already. It WILL produce logic errors that are undetectable.
>>>>>
>>>>> I don’t care much about tracking. Probably, with `if (auto) ...`, you can just rename the variable, but typed non-nullable:
>>>>>
>>>>> ```d
>>>>> void f(int*? p)
>>>>> {
>>>>>      if (int* q = p) ... else return;
>>>>>      int v = *q; // no error, q isn’t nullable, not by analysis, just by type
>>>>> }
>>>>> ```
>>>>
>>>> What matters here is that you do not need to add annotation to the type itself. It only needs to exist within the function signature. Anywhere else its useless information.
>>>
>>> I don’t understand. To me, `Object!` and `Object?` are related but different types. You can have arrays of them, etc., how else would the information of nullableness be retained?
>>>
>>> Maybe I need some info dump on type state analysis and what you mean exactly, because as I understand, TSA would only give you an implicit cast from `T?` to `T!` in some cases, similar to how uniqueness gives you an implicit cast from `T` to `immutable(T)` in some cases.
>>
>> No, it goes in both direction.
>>
>> Type state analysis is based upon a scale, that has a transfer function to go up and down it.
>>
>> You start with unreachable, meaning you cannot read or mutate it. Any access is an error.
>>
>> Next is reachable, you can write to it, but cannot read it. This is void initialized (uninitialized). When a variable declaration is seen this is the default prior to handling the initializer expression.
>>
>> Initialized can be both read and mutated. It is the default in D. For pointers this is the sentinel value null. Aka its nullable. It must not be dereferenced.
>>
>> Non-null is a pointer proven to not be the sentinel value null. It may be dereferenced as well as read/mutated.
>>
>> As you increase in the scale, you get more guarantees, and therefore safety to perform otherwise potentially wrong logic.
>>
>> In such analysis, with a DFA you do it as part of the variables, not the types.
>>
>> ```d
>> int* var;
>> // type state initialized
>>
>> if (var !is null) {
>>     // type state non-null
>> } // type state min(initialized, non-null)
>>
>> var = new int;
>> // type state non-null
>> ```
> 
> So, yes, basically it if TSA can prove a (nullable) pointer definitely isn’t null at some point, at this point, it may be treated like (including converted to) a non-nullable pointer (e.g. copied to one, be dereferenced, etc.).
> 
> I see two concerns:
> - The guarantees might be really weak, i.e. TSA might not be able to prove much in practice when it comes to non-null.
> - It might be hard to explain why a variable is possibly null at some point. If we don’t even have TSA and the error is “`x` is of nullable type” that’s understandable. I have to copy `x` to a variable that’s of non-null type using a language construct that incurs an assertion or check. On the other hand, with TSA, the compiler must assume the programmer expected TSA to prove something non-null, but it couldn’t, and explaining why might be not very insightful and thus not very actionable.

You only need to store converge points to improve the error message significantly. Anything with multiple scopes. Such as switch statement, loops ext. Do that 2 or three times and you should be able to produce a pretty nice error message. However, I won't be implementing that. Somebody else can do it, different skill set that I don't have currently.

> Illustrating the first concern:
> ```d
> int** global;
> 
> void remember(ref int* p) @system { global = &p; }
> 
> void setNull() @system { *global = null; }
> 
> void main() @system
> {
>      int* p = new int;
>      // TSA: p is not null here
>      remember(p);
>      // TSA: p is not null here(?)
>      setNull();
>      // TSA: ???
> }
> ```

Right, to do this, you had to drop out of ``@safe``. Making ``@trusted`` and ``@system`` safe, is not a design goal of D.

With ``@safe`` escape analysis will mark the by-ref parameter as ``scope`` and won't let you escape it, preventing this situation.

> How would TSA “know” that `p` changed after `setNull`? D allows for a lot of action at a distance (mostly because D has pointers).
> 
> My suspicion is that, unfortunately, because TSA has to make conservative assumptions, it’ll have to give us rather weak guarantees after innocuous things happen, like a function call.

No, only when ``@system`` functions are called. It'll be enforced in ``@safe`` and ``@trusted`` should hopefully detect it for when it is called.

> I have some experience with C#’s non-nullable types. If you hover over a variable of reference type, it’ll tell you if the variable can be null (initially surprisingly, even if the variable is typed non-null, but that’s because C#’s non-null annotations are more of a suggestion than a guarantee). I don’t know how many people code D with an editor that has some equivalent of IntelliSense. I don’t.
> 
> Drawing from C#, it also does null analysis for properties. You speak of variables, but what about properties?

Fields, and globals are not supported due to temporal safety. You must perform the load into a function variable before access/mutation.

Even if it was supported, another thread can mutate it from under you after a check (or a known analysis state) and at CT you wouldn't know about it.

> The likely explanation for why that is, is that the non-null state is fragile. An initialized variable won’t ever become uninitialized, not because that’s logically impossible, but the language has no operation that would do that.

In D it would have the ability to, move constructors.

Same with unreachable, loops & goto reset reachability of variables.

> A similar issue is with structs’ `init`. I hate it. C++ has it right here using default constructors. A struct with invariants may have its invariants violated by `init`. It must have a constructor ran over it to be valid. Here, I’d assume TSA could do some work, but again, action at a distance. Only if we disallow resetting a struct with invariants to `init` do we get way. But then, what about moves?

I'm not touching invariants. I view them as good as is.