Dart2JS type inference not converging in some cases

[biggs0125]

Currently Dart2JS has a hardcoded limit on the number of times the type of a specific construct (member, call, etc.) can be refined. This was added as a way to bound the amount of time spent refining the type of any single construct.

During the ongoing efforts to improve performance of type inference in Dart2JS, we've tried to increase (or even remove) this hardcoded limit with the goal of regaining type accuracy lost elsewhere. This uncovered that the hardcoded limit has been hiding an issue where, given the right constraints, some types do not converge to a single value.

This can be seen in sufficiently large programs that make use of the built_value library (usually via protobufs). There is a cycle of ~6 types stemming from BuildJsonSerializers.serialize.

BuildJsonSerializers.serialize contains a call to BuildJsonSerializers._serialize which in turn contains a call back to BuildJsonSerializers.serialize. This mutual recursion on its own is fine. However, it becomes an issue when many different typed objects pass through this serializer (as can be the case when protobufs are used heavily).

At some point the type used to represent the return types of these functions accumulates too many disjoint types and our representation of unions falls back to a generic Object? flat type mask. The problem occurs when further refinement causes a type that was previously flattened to Object? to get turned back into a union type mask representation (by collapsing of some of the disjoint submasks from exact into subclass). Now because these 2 methods are mutually recursive, one has the flattened Object? type and the other has the expanded union type and their internal types are in either of these 2 states. The types then chase each other, flattening and re-expanding repeatedly.

Here is how the types propagate for a full cycle. Notice that at the same time some types are being flattened others are being expanded.

j:method(BuiltJsonSerializers.serialize)
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

InstanceInvocation(InstanceAccessKind.Instance, this.{BuiltJsonSerializers._serialize}(transformedObject, specifiedType))
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

InstanceInvocation(InstanceAccessKind.Instance, this.{BuiltJsonSerializers.serialize}(object))
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

local(BuiltJsonSerializers.serialize#result)
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

j:method(BuiltJsonSerializers._serialize)
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

local(BuiltJsonSerializers.serialize#result)
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

InstanceInvocation(InstanceAccessKind.Instance, this.{BuiltJsonSerializers._serialize}(transformedObject, specifiedType))
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

j:method(BuiltJsonSerializers.serialize)
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

local(BuiltJsonSerializers.serialize#result)
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

InstanceInvocation(InstanceAccessKind.Instance, this.{BuiltJsonSerializers.serialize}(object))
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

local(BuiltJsonSerializers.serialize#result)
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

j:method(BuiltJsonSerializers._serialize)
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

j:method(BuiltJsonSerializers.serialize)
Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool]) -> [null|subclass=Object]

[sigmundch]

Interesting investigation!

I am surprised about some of these transitions. Typically we try to have transitions only in one direction: from more precise, to more conservative/imprecise. So while the move from union to <Object? makes sense, the transition in the other direction seems unintuitive.

[biggs0125]

So the first thing to go from Object? -> union is this:

j:method(BuiltJsonSerializers._serialize)
[null|subclass=Object] -> Union(null, [exact=JSString], [subclass=JSMutableArray], [subclass=JSNumber], [subtype=bool])

The inputs to this are:

(List type Container([exact=JSExtendableArray], element: [null|subclass=Object], length: null), Phi(242029891) null Container([exact=JSExtendableArray], element: [null|subclass=Object], length: null), Call site InstanceInvocation(InstanceAccessKind.Instance, this.{BuiltJsonSerializers.serialize}(object)) on [exact=BuiltJsonSerializers] Union(null, [exact=JSExtendableArray], [exact=JSFixedArray], [exact=JSString]), Phi(376452649) null [null|subclass=JSMutableArray], Phi(652704069) null Union(null, [exact=JSString], [subclass=JSNumber], [subtype=bool]))

On the previous refine (the one that made is Object? the inputs looked like this:

(List type Container([exact=JSExtendableArray], element: [null|subclass=Object], length: null), Phi(242029891) null Container([exact=JSExtendableArray], element: [null|subclass=Object], length: null), Call site InstanceInvocation(InstanceAccessKind.Instance, this.{BuiltJsonSerializers.serialize}(object)) on [exact=BuiltJsonSerializers] Union(null, [exact=JSExtendableArray], [exact=JSFixedArray], [exact=JSString]), Phi(376452649) null Union(null, [exact=JSExtendableArray], [exact=JSFixedArray]), Phi(652704069) null Union(null, [exact=JSString], [subclass=JSInt], [subtype=bool]))

The key difference is Phi(376452649) null Union(null, [exact=JSExtendableArray], [exact=JSFixedArray]) vs. Phi(376452649) null [null|subclass=JSMutableArray]

The first phi includes 2 types ([exact=JSExtendableArray], [exact=JSFixedArray]) + everything else which pushes us over the Union threshold and gets flattened to Object?. The second one only has subclass=JSMutableArray + everything else which brings us back below the Union threshold and we end up back with an explicit Union.

As confirmation of this I bumped up the Union threshold from 4 to 5 and now these types converge. But of course one could construct an example that breaks this for an arbitrarily large threshold.

[biggs0125]

cc @fishythefish @rakudrama

[biggs0125]

One solution I see here is to try to pairwise flatten each of the individual components when flattening a longer list of types. If we combined [exact=JSExtendableArray], [exact=JSFixedArray] into [subclass=JSMutableArray] (the LUB) when we were flattening the first time, then we would've never ended up with Object? in the first place.

I think this is sound and probably provides a more accurate type than finding the LUB of everything being unioned. The issue with this is it might be significantly slower since it'd be O(N^2) for each union (because pairwise) rather than O(N). N is proportional to the number of inputs to the node so this could possibly blow up given the right construction.

[sigmundch]

Interesting. Personally, I never liked these iteration limits and I think it's worth aiming for a monotonic algorithm.

I fear about the pair-wise comparisons as being too expensive too. We used to have more adhoc solutions before (pick pairs in order of the union), but that gave us non-determinism in the past. So we pushed for the LUB of all pieces to ensure consistency and determinism.

Do we benefit from making this more precise? If not, I'd be curious to explore alternatives that we simply don't go back and keep things monotonic. In this case, we could remember we have already reached Object? and not update the type anymore, or remember that a union was deconsturcted and should not be reinstated.

I'm sure there is more behind this to investigate, though. I'm curious though why we are seeing the input phi change from 2 to 1? Are there parts of our algorithm that are inherently non-monotonic? If so, do we still need them?