Nullable tracking in LINQ

[RikkiGibson]

Related to dotnet/roslyn#37468
Related to #3951

Several users have +1'd an issue asking for improved nullable tracking in LINQ (22 at the time of writing). I think it's a sign that we should explore whether to adjust nullable analysis to support more scenarios in this area.

This is more of a "brainstorming" document than a proposal, and I'm posting it in the hope that your feedback will help uncover the problems with it, and help us get a sense of the impact, the risk, and the cost of it.

Note that this document only considers "method-style" LINQ (not using the query syntax). The query syntax works somewhat better because its structure more closely reflects the relationship between successive lambda parameters. It's possible there are scenarios with the query syntax that we'd want to enhance at the same time, but I haven't looked closely at it.

Motivating examples

#nullable enable
using System.Collections.Generic;
using System.Linq;

IEnumerable<string> func1(IEnumerable<string?> input)
{
    // the bog standard case: why do I get a warning here? :(
    return input.Where(s => s != null);
}


class Widget
{
    public string? Prop { get; set; }
}

IEnumerable<string> func2(IEnumerable<Widget> input)
{
    // a slightly more complex case: why do I get a warning here? :(
    return input.Where(w => w.Prop != null).Select(w => w.Prop);
}


List<string> func3(List<string?> input)
{
    // a similar but slightly different case
    return input.Where(s => s != null).ToList();
}


IEnumerable<(string a, string b)> func4(IEnumerable<(string? a, string b)> input)
{
    return input.Where(tuple => tuple.a != null);
}

A framework for analysis

It feels like what we essentially want to do is make it so some linq operators which take predicates or otherwise perform filtering can track the "state" of the collection element across chained operations--think Where, Any, All, Except...

We could do this by making it so calls to certain well-known methods cause us to potentially introduce a slot for the collection element. For example:

IEnumerable<string> func1(IEnumerable<string?> input)
{
    // when we visit the lambda argument to Where, we introduce a slot for the collection element,
    // and for Where() we take the StateWhenTrue at the end of the lambda (joining all return points in the lambda)
    // then use it as the state for the collection element slot.
    input = input.Where(s => != null);

    // we adjust the logic for nullable conversions so that IEnumerable<T?> is permitted to convert to IEnumerable<T>
    // without warning if the collection element slot has not-null flow state.
    // no warning here.
    return input;
}

We may also wish to generalize the change in conversion rules so that more kinds of collections can participate.

void func1(List<string?> list)
{
    if (list.All(s => s != null))
    {
        func2(list); // no warning
    }
}

void func2(List<string> list) { /* ... */ }

One potential formulation: If a type parameter T1 is used as type argument to IEnumerable<T> in the base clause, and the variable has not-null flow state for its collection element, a conversion from nullable to non-nullable type argument is permitted for T1. For example:

public class MyEnumerable<T1, T2> : IEnumerable<T2>
{
    // ...
}

MyEnumerable<string, string> func1(MyEnumerable<string, string?> input)
{
    // we permit the conversion because type parameter T2 is used as type argument to IEnumerable<T>,
    // and the collection element has not-null flow state.
    input.Where(t => t != null);
}

One situation where type would not be subject to the new conversion rule is when the type argument to IEnumerable<T> is not a type parameter from the containing type:

// we use an old reference tuple type for illustration
public class PairCollection<T> : IEnumerable<Tuple<T, T>> { /* ... */ }

void func1(PairCollection<string?> pairs)
{
    if (pairs.All(pair => pair != null))
    {
        func2(pairs); // warning: PairCollection<string?> not convertible to PairCollection<string>
    }
}

void func2(PairCollection<string> pairs) { }

We may also wish to also allow some usages to introduce "doubt" about the collection element and prevent its usage in some scenarios:

List<string> func1(List<string> list)
{
    if (list.Any(x => x == null)) { /* ... */ }

    // warning! collection element has maybe-null flow state.
    // You introduced "doubt" that the collection really consists of non-null elements.
    return list;
}

void func2(List<string?> list)
{
    if (list.All(x => x != null))
    {
        list[3] = null; // should we join the state of this indexer argument into the "collection element" state?
        func3(list); // warning

        list[1] = null;
        list[2] = "abc"; // it's just a join, so this doesn't move the collection element state from MaybeNull back to NotNull.
        func3(list); // warning

        list[1] = null;
        list[1] = "abc"; // this also doesn't move the collection element state back to NotNull.
        func3(list); // warning

        list.Add(null);
        func3(list); // warning
    }
}

void func3(List<string> list) { /* ... */ }

It feels problematic to enumerate every possible way to mutate a collection element. Just going by conventions doesn't feel adequate, especially since things can simply be mutated, particularly indirectly

void func1(List<string?> list)
{
    if (list.All(x => x != null))
    {
        func2(list);
        func3(list);
    }
}

void func2(List<string?> list) { list.Add(null); }

void func3(List<string> list) { /* ... */ }

I think what we will want to do is: do our best to address the greater part of users issues, but limit the analysis of conversions to when the thing is used as an IEnumerable<T>.

Alternatively, whenever the thing is used as an IEnumerable<T?>, we re-introduce doubt that the collection really contains non-nullable elements.

Alternatively, we could limit the lifetime of the collection element slot so that it is discarded when we finish visiting a call chain. (is that practical? and is it desirable?)

Detecting operators and their relevant behaviors

At a glance it doesn't seem like it would be useful to introduce special flow analysis attributes for every kind of behavior that can be produced by a LINQ operator. I think you'd end up with very few usages of each attribute. If we did this feature it would probably involve some special recognition of LINQ operators. There is some precedent with this with IEquatable<T>.Equals(T) and other well-known methods.

[svick]

I think this is definitely something that should be improved. Though it does seem to be fairly narrow, which makes me ask some questions:

1. You mention "certain well-known methods". Does that mean e.g. Enumerable.Where specifically, or would it be more like "a method called Where with the right shape"? Specifically, would it support Rx.Net Observable.Where?

2. What about the recently accepted Enumerable.Match (Add an Enumerable.Match method runtime#39443 (comment))? For example, consider the following code:

   void func(IEnumerable<(string? a, string b)> input)
   {
       var lists = input.Match(tuple => tuple.a != null);
   }
   

   Would the type/null state of lists somehow be the expected (List<(string a, string b)> Matched, List<(string? a, string b)> Unmatched)?

[RikkiGibson]

You mention "certain well-known methods". Does that mean e.g. Enumerable.Where specifically, or would it be more like "a method called Where with the right shape"? Specifically, would it support Rx.Net Observable.Where?

Good question. If I were to prototype the change I'd make it recognize specific methods in the Enumerable class. If it made it beyond that point then we'd probably want to introduce a way to signal to the compiler that "these methods are LINQ operators".

What about the recently accepted Enumerable.Match (dotnet/runtime#39443 (comment))?

My expectation is that the return type of the input.Match call is still (List<(string? a, string b)> Matched, List<(string? a, string b)> Unmatched). However the slot structure (ignoring slots for value types) could look like:

• root:
  • Matched:
    • "Element":
      • a: not-null
      • b: not-null
  • Unmatched:
    • "Element":
      • a: maybe-null
      • b: not-null

If the return value is converted to (List<(string a, string b)> Matched, List<(string? a, string b)> Unmatched), the compiler would need to traverse this slot structure somehow in order to decide whether to give a warning.

At this point it's still very speculative, though, because:

1. introducing a slot for the return value of a call isn't something that we've done before (IIRC).
2. allowing nullable-variant conversions when the type parameters aren't variant, such as in List<T>, seems more and more questionable the more I think about it.

[canton7]

List<string> func3(List<string?> input)
{
    // a similar but slightly different case
    return input.Where(s => s != null).ToList();
}

That one makes my slightly uncomfortable. IEnumerable<T> is covarient, so it doesn't matter if you return an IEnumerable<T> when the user actually wanted an IEnumerable<T?>. List<T> isn't: naively making ToList() return a List<string> in your example would break anyone who wrote List<string?> func3(List<string?> input), and it's annoying for anyone who wanted a List<string?>.

I don't have a good answer to this however. I don't have a good feelling for how common this would be, and I don't have any suggestions for avoiding it as an issue!

[RikkiGibson]

The suggestion here is that .ToList() actually still returns List<string?> in this scenario, but that the compiler may track sufficiently detailed flow state that when it is converted to List<string>, the compiler may realize that no warning needs to be issued.

However, it's not clear to me whether allowing such conversions on types like List is really something we should do. It feels like it has a lot of potential to introduce safety issues, strange "cliffs" in what the compiler does and doesn't recognize, and user confusion.