Add a type for objects with typed properties.

Add a type for objects with typed properties.

asm.js assumes a standard library object, exposing a subset of window +
window.Math, will be passed to modules.
Expanding the type system to allow an object with an explicitly typed set of
named properties.

Adding a test of object types to test-types.

LOG=N
BUG= https://code.google.com/p/v8/issues/detail?id=4203
TEST=test-types
R=rossberg@chromium.org,titzer@chromium.org

[bradn, 2015-07-01 01:36:25]

Any thoughts on naming with this?
I'm a little concerned "Object" is overused generally.

[rossberg, 2015-07-01 08:05:40]

Yeah, unfortunately, it won't be that simple. You will need to extend almost all
operations in types.cc to handle the new kind of type, in order to implement the
right algebraic properties. This will become apparent ones you extend the Fuzz
function in types-fuzz.h to actually generate Object types -- I expect that most
of test-types will start failing. (You may want to locally run the tests with
increased fuzz count of 200 at types-fuzz.h:117 to converge faster with more
coverage.) Various tests also have explicit cases for some manually chosen
types, you should extend those with combinations involving the new type.

But beware, this will be quite tricky. Given that this is only for typing one
asm parameter, I'm not sure building it deep into the type system is the best
way forward. I'd suggest a different route: since the object is only used in the
asm module's "imports" you should be able to recognise and handle those
syntactically directly in the asm checker.

On 2015/07/01 01:36:25, bradn wrote:
> Any thoughts on naming with this?
> I'm a little concerned "Object" is overused generally.

I'd be fine with Object, it is what it is.

[bradn, 2015-07-01 12:16:57]

Thank Andreas, that might explain some of the oddnesses I've encountered
applying this!

Since use of properties is carefully constrained in asm.js, doing things in
VisitProperty probably can work. I'll explore more.

Some other type system questions:

* Should Function(R, S, T0, T1...) types be unionable with each other? (I.e. can
I use them to express the overloaded nature of Math.abs etc?) Some care will be
required at a VisitCall to disentangle which concrete version is relevant.
UnionType seems to be considered an implementation internal. Would adding a way
to iterate over union members be ok?

* Should a function like fround ( Undefined \/ float32 \/ float64 -> float32)
work as expected?

* Should Arrays of a single Function type work correctly?

* Any recommendations on how to represent an ArrayBuffer? I may be able to avoid
this one, though, as the spec does not seem to permit variables of this type
other than the module parameter, so I could special case it.

* I think ArrayBuffer might not need to be expressed, but in general is there
some way I've missed to express a sentinel type (i.e. something that won't
quietly slip by union/intersect but can be checked for explicitly?)

* I want to double check using the types.h types makes sense for asm
validation/typing?

Before you'd pointed me at your CL I'd been going down the road of a type system
local to asm validation, mirroring the typing rules and types (intish etc) in
the asm.js spec. I had figured on converting to types.h types as each ast node
is visited, since with asm, at each step concrete types are known, and type
unions less critical.

So far it seems like using types.h allows for a safe superset of asm.js, and
does seem to be a good deal more concise than where adding another type system
was going.

[rossberg, 2015-07-01 17:47:23]

On 2015/07/01 12:16:57, bradn wrote:
> Some other type system questions:
> 
> * Should Function(R, S, T0, T1...) types be unionable with each other? (I.e.
can
> I use them to express the overloaded nature of Math.abs etc?) Some care will
be
> required at a VisitCall to disentangle which concrete version is relevant.

Overloading is intersection, not union. In some cases, this can be converted to
union on the argument types (using distributivity over the functional
implication), but not in general. In particular, there is no way to represent
the overloading of Math.abs,

  (int -> int) /\ (double -> double)

with union only.

Unfortunately, our type system cannot represent arbitrary intersections. (It is
a well-known result in type theory that adding both union + intersection types
to a type system leads to combinatorial explosion that you want to avoid at all
cost.)

So function types themselves can be unioned, but that isn't what you want, and
not very useful. For all cases but Math.abs that occur in asm.js you can get
away with unioning the arguments, though. I'd simply try to handle Math.abs as a
special case (like asm already does for operators).

> UnionType seems to be considered an implementation internal. Would adding a
way
> to iterate over union members be ok?

No, that's intentionally not provided (other than the iteration over classes and
constants, which is already kind of fishy). Because of the above, it probably
wouldn't help you either.

> * Should a function like fround ( Undefined \/ float32 \/ float64 -> float32)
> work as expected?

I think so, although I'm not entirely sure what you mean by "as expected". :)

> * Should Arrays of a single Function type work correctly?

Yes. All the types should be fully compositional.

> * Any recommendations on how to represent an ArrayBuffer? I may be able to
avoid
> this one, though, as the spec does not seem to permit variables of this type
> other than the module parameter, so I could special case it.

Until recently there actually was a (bitset) type for that, but we removed it
because of bit pressure.

If you can get away without for now, that would be easiest. We still have to
solve the bit issue mid-term, however.

> * I think ArrayBuffer might not need to be expressed, but in general is there
> some way I've missed to express a sentinel type (i.e. something that won't
> quietly slip by union/intersect but can be checked for explicitly?)

The easiest is a bit, which we don't have. :) Other than that, we probably want
to add a structural type for Sentinels in the future.

In some cases you might get away with creating a sentinel Class over some dummy
map for the time being (or a dummy Constant). Depends on what you need to
express. What else besides ArrayBuffer?

> * I want to double check using the types.h types makes sense for asm
> validation/typing?
> 
> Before you'd pointed me at your CL I'd been going down the road of a type
system
> local to asm validation, mirroring the typing rules and types (intish etc) in
> the asm.js spec. I had figured on converting to types.h types as each ast node
> is visited, since with asm, at each step concrete types are known, and type
> unions less critical.
> 
> So far it seems like using types.h allows for a safe superset of asm.js, and
> does seem to be a good deal more concise than where adding another type system
> was going.

Yes, I'd strongly prefer using the existing types. Especially since you'll
probably need to forward them to the Turbofan backend in some form anyway. Most
of what you are missing from the types currently is needed elsewhere as well, so
we strongly want to resolve it. (We are currently discussing e.g. the bit
issue.)

[titzer, 2016-03-10 10:14:55]

On 2015/07/01 17:47:23, rossberg wrote:
> On 2015/07/01 12:16:57, bradn wrote:
> > Some other type system questions:
> > 
> > * Should Function(R, S, T0, T1...) types be unionable with each other? (I.e.
> can
> > I use them to express the overloaded nature of Math.abs etc?) Some care will
> be
> > required at a VisitCall to disentangle which concrete version is relevant.
> 
> Overloading is intersection, not union. In some cases, this can be converted
to
> union on the argument types (using distributivity over the functional
> implication), but not in general. In particular, there is no way to represent
> the overloading of Math.abs,
> 
>   (int -> int) /\ (double -> double)
> 
> with union only.
> 
> Unfortunately, our type system cannot represent arbitrary intersections. (It
is
> a well-known result in type theory that adding both union + intersection types
> to a type system leads to combinatorial explosion that you want to avoid at
all
> cost.)
> 
> So function types themselves can be unioned, but that isn't what you want, and
> not very useful. For all cases but Math.abs that occur in asm.js you can get
> away with unioning the arguments, though. I'd simply try to handle Math.abs as
a
> special case (like asm already does for operators).
> 
> > UnionType seems to be considered an implementation internal. Would adding a
> way
> > to iterate over union members be ok?
> 
> No, that's intentionally not provided (other than the iteration over classes
and
> constants, which is already kind of fishy). Because of the above, it probably
> wouldn't help you either.
> 
> > * Should a function like fround ( Undefined \/ float32 \/ float64 ->
float32)
> > work as expected?
> 
> I think so, although I'm not entirely sure what you mean by "as expected". :)
> 
> > * Should Arrays of a single Function type work correctly?
> 
> Yes. All the types should be fully compositional.
> 
> > * Any recommendations on how to represent an ArrayBuffer? I may be able to
> avoid
> > this one, though, as the spec does not seem to permit variables of this type
> > other than the module parameter, so I could special case it.
> 
> Until recently there actually was a (bitset) type for that, but we removed it
> because of bit pressure.
> 
> If you can get away without for now, that would be easiest. We still have to
> solve the bit issue mid-term, however.
> 
> > * I think ArrayBuffer might not need to be expressed, but in general is
there
> > some way I've missed to express a sentinel type (i.e. something that won't
> > quietly slip by union/intersect but can be checked for explicitly?)
> 
> The easiest is a bit, which we don't have. :) Other than that, we probably
want
> to add a structural type for Sentinels in the future.
> 
> In some cases you might get away with creating a sentinel Class over some
dummy
> map for the time being (or a dummy Constant). Depends on what you need to
> express. What else besides ArrayBuffer?
> 
> > * I want to double check using the types.h types makes sense for asm
> > validation/typing?
> > 
> > Before you'd pointed me at your CL I'd been going down the road of a type
> system
> > local to asm validation, mirroring the typing rules and types (intish etc)
in
> > the asm.js spec. I had figured on converting to types.h types as each ast
node
> > is visited, since with asm, at each step concrete types are known, and type
> > unions less critical.
> > 
> > So far it seems like using types.h allows for a safe superset of asm.js, and
> > does seem to be a good deal more concise than where adding another type
system
> > was going.
> 
> Yes, I'd strongly prefer using the existing types. Especially since you'll
> probably need to forward them to the Turbofan backend in some form anyway.
Most
> of what you are missing from the types currently is needed elsewhere as well,
so
> we strongly want to resolve it. (We are currently discussing e.g. the bit
> issue.)

Is this issue now obsolete with our validator?

[bradn, 2016-03-14 00:46:54]

So I ended up doing roughly what Andreas suggested.
For example Abs is a Number -> Number
But when it's actually encountered, there's a direct check on each of the
parameters making it polymorphic at the specific site.

One thing there isn't as much of as there shoud be, is testing around this.
Will send you some additional tests.

[bradn, 2016-03-14 00:47:05]

Adding more tests did turn up an intedirectly related issue.
+fround(x) wasn't begin handled correctly. :-(

[bradn, 2016-03-14 00:47:12]

Closing.