Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2208233002:
Make LUB algorithm aware of non-null types (Closed)
|
Created:
4 years, 4 months ago by stanm Modified:
4 years, 4 months ago CC:
reviews_dartlang.org Base URL:
https://github.com/dart-lang/sdk@nnp Target Ref:
refs/heads/master Visibility:
Public. |
DescriptionMake LUB algorithm aware of non-null types
In addition to the functional change I added some more tests to test for
regressions and for the new behaviour.
BUG=
R=jmesserly@google.com
Committed: https://github.com/dart-lang/sdk/commit/f3f10a6dd6d996dddc3f6d1dfb2410c2c2e86f31
Patch Set 1 #
Total comments: 5
Patch Set 2 : Update LUB #Patch Set 3 : Optimize return paths #Patch Set 4 : Outline common functionality #Patch Set 5 : Rename for clarity #
Total comments: 4
Patch Set 6 : Fix logic bug in isNullableType #
Depends on Patchset: Messages
Total messages: 19 (5 generated)
stanm@google.com changed reviewers: + jmesserly@google.com, vsm@google.com
jmesserly@google.com changed reviewers: + leafp@google.com
+Leaf ... offhand this doesn't feel right to me. I would expect LUB(⊥, x) == x for all x. (there is a comment to this effect in getLeastUpperBound) Given a type S, I would expect LUB(!S, null) == ?S. Since we can't represent ?int, Object would be the next closest thing.
On 2016/08/03 22:40:41, John Messerly wrote: > +Leaf ... offhand this doesn't feel right to me. > > I would expect LUB(⊥, x) == x for all x. (there is a comment to this effect in > getLeastUpperBound) > > Given a type S, I would expect LUB(!S, null) == ?S. Since we can't represent > ?int, Object would be the next closest thing. BTW, you will probably need to change the type of `null` literal to not be ⊥, because pretending it's bottom doesn't work once we have non-nullable types. (even in Dart1, it felt like a hack to me.)
https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/genera... File pkg/analyzer/lib/src/generated/type_system.dart (right): https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/genera... pkg/analyzer/lib/src/generated/type_system.dart:151: if (type1.isBottom && isNonNullableType(type2)) { This depends a bit on exactly what system you are trying to implement, but my suggestion would be that you start with something like this: BOT is the true bottom type (uninhabited). This can't be expressed in Dart, but it lets us talk about some things. T? is a nullable T. It is essentially T or null. T! is a non-nullable T. It is essentially T, without null if T is nullable. Obviously, there is some initial set of types which are either nullable or non-nullable. My guess is that you are implementing a system in which the only user visible types are, in fact, that initial set. Then in Dart: bottom =def= BOT? - that is, the Dart bottom type is either BOT (i.e. nothing) or null. i.e., BOT? is inhabited only by null. then the definition of LUB here falls out. LUB(S?, T?) = LUB(S, T)? LUB(S!, T!) = LUB(S, T)! LUB(S?, T!) = LUB(S, T)? LUB(S!, T?) = LUB(S, T)? You don't have actual syntax for ? and !, I presume, but basically its the same thing - you just have an enumerated list of types which are nullable and non-nullable. This means that you can't necessarily construct the direct LUB as defined above. For example, if int is your only non-nullable type, and you don't have a way of writing int?, then LUB(bottom, int) is the least type which is a supertype of int, but which is nullable. If num is nullable, then the answer should be num. Otherwise probably Object. Let me know if you want to talk this through offline. https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/task/s... File pkg/analyzer/lib/src/task/strong/checker.dart (right): https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/task/s... pkg/analyzer/lib/src/task/strong/checker.dart:848: if (rules.isNonNullableType(type) && !rules.isNonNullableType(exprType)) { I'd suggest a helper "isNullableType", to avoid double negation bugs.
https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/genera... File pkg/analyzer/lib/src/generated/type_system.dart (right): https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/genera... pkg/analyzer/lib/src/generated/type_system.dart:151: if (type1.isBottom && isNonNullableType(type2)) { On 2016/08/03 23:45:07, Leaf wrote: > This depends a bit on exactly what system you are trying to implement, but my > suggestion would be that you start with something like this: > > BOT is the true bottom type (uninhabited). This can't be expressed in Dart, but > it lets us talk about some things. > T? is a nullable T. It is essentially T or null. > T! is a non-nullable T. It is essentially T, without null if T is nullable. > > Obviously, there is some initial set of types which are either nullable or > non-nullable. My guess is that you are implementing a system in which the only > user visible types are, in fact, that initial set. > > Then in Dart: > > bottom =def= BOT? > - that is, the Dart bottom type is either BOT (i.e. nothing) or null. i.e., > BOT? is inhabited only by null. > > then the definition of LUB here falls out. > > LUB(S?, T?) = LUB(S, T)? > LUB(S!, T!) = LUB(S, T)! > LUB(S?, T!) = LUB(S, T)? > LUB(S!, T?) = LUB(S, T)? > > You don't have actual syntax for ? and !, I presume, but basically its the same > thing - you just have an enumerated list of types which are nullable and > non-nullable. This means that you can't necessarily construct the direct LUB as > defined above. For example, if int is your only non-nullable type, and you > don't have a way of writing int?, then LUB(bottom, int) is the least type which > is a supertype of int, but which is nullable. If num is nullable, then the > answer should be num. Otherwise probably Object. > > Let me know if you want to talk this through offline. Thanks for the detailed explanation. If by 'My guess is that you are implementing a system in which the only user visible types are, in fact, that initial set.' you mean that I don't consider the case of additional types being added to the system at runtime, then your guess is correct. I think I just completely ignored the fact we're looking for a **lower** upper bound. This is what I intent to do: LUB(S?, T?) = LUB(S, T)? LUB(S!, T!) = LUB(S, T)! LUB(S?, T!) = LUB(S?, LNST(T)?) = LUB(S, LNST(T))? LUB(S!, T?) = LUB(LNST(S)?, T?) = LUB(LNST(S), T)? where LNST(T)? is the least nullable super type of T. If T? exists for T! then LNST(T)? is T?. Otherwise, I need to search the set of all super types of T and return the one that has longest inheritance path to object (borrowed logic from computeLeastUpperBound). Do you think that should work? https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/task/s... File pkg/analyzer/lib/src/task/strong/checker.dart (right): https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/task/s... pkg/analyzer/lib/src/task/strong/checker.dart:848: if (rules.isNonNullableType(type) && !rules.isNonNullableType(exprType)) { On 2016/08/03 23:45:07, Leaf wrote: > I'd suggest a helper "isNullableType", to avoid double negation bugs. Good idea, thanks!
John: if I go down the path of changing the static type of null, I think that will quickly snowball and I will end up doing general NNBD. What do you think?
Description was changed from ========== Least upper bound(null, non-nullable) = dynamic In addition to the functional change I added some more tests to test for regressions and for the new behaviour. BUG= ========== to ========== Least upper bound(null, non-nullable) = dynamic In addition to the functional change I added some more tests to test for regressions and for the new behaviour. BUG= ==========
Description was changed from ========== Least upper bound(null, non-nullable) = dynamic In addition to the functional change I added some more tests to test for regressions and for the new behaviour. BUG= ========== to ========== Make LUB algorithm aware of non-null types In addition to the functional change I added some more tests to test for regressions and for the new behaviour. BUG= ==========
I think I'm happier with the current implementation. PTAL
On 2016/08/04 00:32:42, stanm wrote: > John: if I go down the path of changing the static type of null, I think that > will quickly snowball and I will end up doing general NNBD. What do you think? Well in strong mode, we could infer it from the surrounding context type. I've come close to fixing that a few times, as we'd get less "type inferred as bottom" bugs that way :) I'm working on a CL to try that out now ... the patch is easy, but it looks like lots of test expectations to update. Another option is to introduce a type for the null literal that is a subtype of other nullable types, but is not bottom.
https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... File pkg/analyzer/lib/src/generated/type_system.dart (right): https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... pkg/analyzer/lib/src/generated/type_system.dart:800: return type is FunctionType || is this supposed to say: `type is! FunctionType &&` it seems to be saying all function types are not-nullable. suggestion: remove this method. Instead, only implement isNullableType. Easier to reason about when there's not a negation in the method name.
On 2016/08/04 12:43:46, John Messerly wrote: > On 2016/08/04 00:32:42, stanm wrote: > > John: if I go down the path of changing the static type of null, I think that > > will quickly snowball and I will end up doing general NNBD. What do you think? > > Well in strong mode, we could infer it from the surrounding context type. I've > come close to fixing that a few times, as we'd get less "type inferred as > bottom" bugs that way :) > I'm working on a CL to try that out now ... the patch is easy, but it looks like > lots of test expectations to update. https://codereview.chromium.org/2210293002/, although I'm having second thoughts on it now, so that would leave the option below > Another option is to introduce a type for the null literal that is a subtype of > other nullable types, but is not bottom.
LGTM w/ a fix for the FunctionType issue https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... File pkg/analyzer/lib/src/generated/type_system.dart (right): https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... pkg/analyzer/lib/src/generated/type_system.dart:800: return type is FunctionType || On 2016/08/04 12:48:18, John Messerly wrote: > is this supposed to say: `type is! FunctionType &&` > > it seems to be saying all function types are not-nullable. > > suggestion: remove this method. Instead, only implement isNullableType. Easier > to reason about when there's not a negation in the method name. actually looking at this again, maybe assert that `type is InterfaceType`? that seems to be assumed by the code that uses it.
https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... File pkg/analyzer/lib/src/generated/type_system.dart (right): https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... pkg/analyzer/lib/src/generated/type_system.dart:800: return type is FunctionType || On 2016/08/04 12:48:18, John Messerly wrote: > is this supposed to say: `type is! FunctionType &&` > > it seems to be saying all function types are not-nullable. > > suggestion: remove this method. Instead, only implement isNullableType. Easier > to reason about when there's not a negation in the method name. Aw, yes, silly mistake. I'd prefer if there was a simpler name for "non-nullable" - I think of it as a unit concept - but I can't think of anything else so I'll do as you suggested. I'll leave the comments as is, because I think they make more sense the way they are. https://codereview.chromium.org/2208233002/diff/80001/pkg/analyzer/lib/src/ge... pkg/analyzer/lib/src/generated/type_system.dart:800: return type is FunctionType || On 2016/08/04 18:43:41, John Messerly wrote: > On 2016/08/04 12:48:18, John Messerly wrote: > > is this supposed to say: `type is! FunctionType &&` > > > > it seems to be saying all function types are not-nullable. > > > > suggestion: remove this method. Instead, only implement isNullableType. Easier > > to reason about when there's not a negation in the method name. > > actually looking at this again, maybe assert that `type is InterfaceType`? that > seems to be assumed by the code that uses it. Done.
Description was changed from ========== Make LUB algorithm aware of non-null types In addition to the functional change I added some more tests to test for regressions and for the new behaviour. BUG= ========== to ========== Make LUB algorithm aware of non-null types In addition to the functional change I added some more tests to test for regressions and for the new behaviour. BUG= R=jmesserly@google.com Committed: https://github.com/dart-lang/sdk/commit/f3f10a6dd6d996dddc3f6d1dfb2410c2c2e86f31 ==========
Message was sent while issue was closed.
Committed patchset #6 (id:100001) manually as f3f10a6dd6d996dddc3f6d1dfb2410c2c2e86f31 (presubmit successful).
Message was sent while issue was closed.
lgtm https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/genera... File pkg/analyzer/lib/src/generated/type_system.dart (right): https://codereview.chromium.org/2208233002/diff/1/pkg/analyzer/lib/src/genera... pkg/analyzer/lib/src/generated/type_system.dart:151: if (type1.isBottom && isNonNullableType(type2)) { On 2016/08/04 00:31:15, stanm wrote: > On 2016/08/03 23:45:07, Leaf wrote: > > This depends a bit on exactly what system you are trying to implement, but my > > suggestion would be that you start with something like this: > > > > BOT is the true bottom type (uninhabited). This can't be expressed in Dart, > but > > it lets us talk about some things. > > T? is a nullable T. It is essentially T or null. > > T! is a non-nullable T. It is essentially T, without null if T is nullable. > > > > Obviously, there is some initial set of types which are either nullable or > > non-nullable. My guess is that you are implementing a system in which the > only > > user visible types are, in fact, that initial set. > > > > Then in Dart: > > > > bottom =def= BOT? > > - that is, the Dart bottom type is either BOT (i.e. nothing) or null. i.e., > > BOT? is inhabited only by null. > > > > then the definition of LUB here falls out. > > > > LUB(S?, T?) = LUB(S, T)? > > LUB(S!, T!) = LUB(S, T)! > > LUB(S?, T!) = LUB(S, T)? > > LUB(S!, T?) = LUB(S, T)? > > > > You don't have actual syntax for ? and !, I presume, but basically its the > same > > thing - you just have an enumerated list of types which are nullable and > > non-nullable. This means that you can't necessarily construct the direct LUB > as > > defined above. For example, if int is your only non-nullable type, and you > > don't have a way of writing int?, then LUB(bottom, int) is the least type > which > > is a supertype of int, but which is nullable. If num is nullable, then the > > answer should be num. Otherwise probably Object. > > > > Let me know if you want to talk this through offline. > > Thanks for the detailed explanation. > > If by 'My guess is that you are implementing a system in which the only user > visible types are, in fact, that initial set.' you mean that I don't consider > the case of additional types being added to the system at runtime, then your > guess is correct. > > I think I just completely ignored the fact we're looking for a **lower** upper > bound. This is what I intent to do: > > LUB(S?, T?) = LUB(S, T)? > LUB(S!, T!) = LUB(S, T)! > LUB(S?, T!) = LUB(S?, LNST(T)?) = LUB(S, LNST(T))? > LUB(S!, T?) = LUB(LNST(S)?, T?) = LUB(LNST(S), T)? > > where LNST(T)? is the least nullable super type of T. If T? exists for T! then > LNST(T)? is T?. Otherwise, I need to search the set of all super types of T and > return the one that has longest inheritance path to object (borrowed logic from > computeLeastUpperBound). > > Do you think that should work? Looks right to me. LNST(T)? == LNST(T), I think, but doesn't matter. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
