Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Invalid analyzer error #19282

Closed
DartBot opened this issue Jun 6, 2014 · 11 comments
Closed

Invalid analyzer error #19282

DartBot opened this issue Jun 6, 2014 · 11 comments
Labels
area-language New language issues should be filed at https://github.com/dart-lang/language P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug

Comments

@DartBot
Copy link

DartBot commented Jun 6, 2014

This issue was originally filed by ovangle...@gmail.com


Since 1.4.2, when analysing the following (awful, but valid) code

    List<int> foo(int i) => (i == 0 ? [] : foo(i - 1))..add(i);

the analyzer reports an error

    "The method 'add' is not defined for the class 'EfficientLength'".

@bwilkerson
Copy link
Member

Yes. Believe it or not, this was actually a bug fix; the warning is correct and the lack of a warning was the bug.

According to the specification, the static type of a conditional expression ("i == 0 ? [] : foo(i - 1)") is the least upper bound (LUB) of the types of the then- and else-expressions. Those types are List<dynamic> and List<int> respectively, and the LUB of those is EfficientLength. And because EfficientLength does not implement 'add', the warning is valid.


Set owner to @bwilkerson.
Added this to the 1.5 milestone.
Removed Priority-Unassigned label.
Added Priority-Medium, Area-Analyzer, Invalid labels.

@DartBot
Copy link
Author

DartBot commented Jun 7, 2014

This comment was originally written by ova...@gmail.com


I would have thought the LUB of List<A> and List<B> was the LUB of A and B, in this case dynamic.

@DartBot
Copy link
Author

DartBot commented Jun 7, 2014

This comment was originally written by ovan...@gmail.com


Sorry, more correctly, that would be:

The LUB of List<A> and List<B> would be List<LUB(A,B)>, in this case, LUB(int,dynamic) = dynamic, so the correct bound should have been List<dynamic>, which does implement ‘add’.

Why is this reasoning wrong?

@bwilkerson
Copy link
Member

The LUB of List<A> and List<B> would be List<LUB(A,B)>, in this case, LUB(int,dynamic) = dynamic,
so the correct bound should have been List<dynamic>, which does implement ‘add’.

You, and most of the world, would have expected that.

Why is this reasoning wrong?

Simple answer: because that's not what the specification states (see section 18.8.2). :-)

A more complete answer is that this reasoning only works in some cases. The code above is fine because the type of 'i' is 'int'. If you changed the type of 'i' to anything else it would no longer be correct, even though the definition of LUB you proposed would still result in there being no warning. So, a 'List<int>' can be used where a 'List<dynamic>' is expected if you are only extracting elements from the list (because every element will be an 'int' and hence a 'dynamic') but not if you are adding to the list (because it's fine to add a 'String' to a 'List<dynamic>' but not to a 'List<int>').

@peter-ahe-google
Copy link
Contributor

The specification is written by humans and may contain bugs. It is important that implementors are always critical of clearly ridiculous behavior.

Clearly, any reasonable person would expect that the static type should be List<dynamic>, even if we try to short-circuit the LUB computation of type arguments.


Removed the owner.
Removed this from the 1.5 milestone.
Removed Area-Analyzer label.
Added Area-Language, Triaged labels.

@peter-ahe-google
Copy link
Contributor

cc @johnniwinther.
cc @bwilkerson.

@johnniwinther
Copy link
Member

In general, least upper bound is not a good choice for the typing of conditionals given the bivariance of our assignability.

If the static types of the expressions are closely related a good least upper bound is of some use. For instance the static type of this condition:

List<int> l = b ? [] : <int>[];

should be probably be List<dynamic> or List<int>. This will make the expression assignable to List<int> and more importantly you can do

(b ? [] : <int>[])..add(0)

without warning because the List-ishness is preserved.

On the other hand, if the static types of the expressions are not related the use of least upper bound works against the assignability. For instance

List list = b ? [] : 0;

is ok since the least upper bound of List and int is Object and Object is assignable to List.

The best typing of a conditional, given the typing rules of Dart, is a union-type-like static typing in which the assignment of a conditional, like a = b ? c : d, is checked by checking that both c and d are assignable to a, and in which property access on a conditional, like (b ? c : d).foo, is checked by checking that both c and d have the property foo. Such a solution is complicated since it will potentially drag in real union types into the type system -- for instance when trying to give a good static type to the expression (b ? c : d).foo when c.foo and d.foo have different types.

The current definition of least upper bound for interface types is based on a hierarchical ordering of the supertypes of the types for which we try to find the most specific common type that is unique.

For instance for the least upper bound of List<int> and List<dynamic> we compute:

Supertypes for List<int> by depth:
0: Object
1: Iterable<int>, EfficientLength
2: List<int>

and supertypes for List<dynamic> by depth:
0: Object
1: Iterable<dynamic>, EfficientLength
2: List<dynamic>

The common supertypes are (by depth)
0: Object
1: EfficientLength

and EfficientLength is chosen because it's the most specific.

I propose a pragmatic solution that will improve the handling of generic types:

Instead of computing the least upper bound for interface directly on types but instead on declarations we will compute the superdeclarations by depth for both List<dynamic> and List<int> to be:

0: Object
1: Iterable, EfficientLength
2: List

We choose List as the most specific declaration. Since List is generic we want to find its type arguments. The naive approach is to apply algorithm recursively but (in strange cases) this can lead to infinite computations and/or recursive types so we don't go down that path.

Instead, to get something of value, we use the more specific relation, <<, to find the type arguments of the most specific declaration: For each type variable, if one of the type arguments is less specific than all other we choose this, otherwise we choose dynamic. In the example, since int << dynamic, we then find List<dynamic> to be the least upper bound.

This solution will not aid in finding problems like List list = b ? [] : 0; but it will remove some of the annoying false positives encountered for generic types.


cc @gbracha.

@lrhn
Copy link
Member

lrhn commented Jun 12, 2014

I like Johnni's suggestion, and after looking at it, I agree that picking the least specific of the type parameters is the right thing.

The problem with using most-specific vs least-specific is the usual co-/contra-variance problem.

For a List<int>/List<num> unification, picking the most specific type (List<int>) will not only allow you to add integers, but it will also claim that all elements extracted from the list are integers, which isn't preserved by List<Object>. Picking List<Object> has the opposite behavior.

The difference is whether you get a warning for:
   int x = (q?<int>[1]:<num>[1.5])[0]; // warning if picking least specific type.
or for:
   (q?<int>[1]:<num>[1.5]).add(2.5) // warning if picking most specific type.

I would prefer the approach that gives a warning for the former case. Modification can fail if you have the wrong type (lists could be unmodifiable too), but you should be able to trust the type of values coming out of a collection.

For Dart's static type inference, we generally err on the side of co-variance.

@gbracha
Copy link
Contributor

gbracha commented Jun 12, 2014

We can revisit this at some point and present a proposal to TC52. I would urge caution. There will always be individual cases that seem absurd given the nature of Dart's types. The system is not sound, so there is no incontrovertible logic we must follow. This is both a strength and a weakness,


Set owner to @gbracha.
Added Accepted label.

@peter-ahe-google
Copy link
Contributor

The only incontrovertible logic we need to follow is that the results we compute aren't completely insane ;-)

The current behavior fails completely for generic types. The current behavior is so bad that it would be better to have a rule which said that the type of a conditional is dynamic.

@DartBot DartBot added Type-Defect area-language New language issues should be filed at https://github.com/dart-lang/language labels Jun 12, 2014
@kevmoo kevmoo added P2 A bug or feature request we're likely to work on type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) and removed accepted labels Feb 29, 2016
@lrhn lrhn added type-enhancement A request for a change that isn't a bug and removed type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) labels Jun 22, 2018
@natebosch
Copy link
Member

The example no longer produces an error. I'm pretty sure this was fixed by #25821

We can reopen if there is a more up to date example

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-language New language issues should be filed at https://github.com/dart-lang/language P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug
Projects
None yet
Development

No branches or pull requests

8 participants