Basic interface inference for modules.

Basic interface inference for modules.

All module expressions, and all variables that might refer to modules,
are assigned interfaces (module types) that are resolved using
unification. This is necessary to deal with the highly recursive
nature of ES6 modules, which does not allow any kind of bottom-up
strategy for resolving module names and paths.

Error messages are rudimental right now. Probably need to track
more information to make them nicer.

R=svenpanne@chromium.org
BUG=v8:1569
TEST=

Committed: https://code.google.com/p/v8/source/detail?r=10966

[Sven Panne, 2012-03-08 08:55:00]

http://codereview.chromium.org/9615009/diff/1/src/ast.h
File src/ast.h (right):

http://codereview.chromium.org/9615009/diff/1/src/ast.h#newcode614
src/ast.h:614: explicit ModuleLiteral(Block* body, Interface* interface)
Remove "explicit".

http://codereview.chromium.org/9615009/diff/1/src/ast.h#newcode2519
src/ast.h:2519: // Out-of-line inline constructors.
I guess this here for cyclic dependencies reasons, so a remark in the comment
would be nice.

http://codereview.chromium.org/9615009/diff/1/src/interface.cc
File src/interface.cc (right):

http://codereview.chromium.org/9615009/diff/1/src/interface.cc#newcode48
src/interface.cc:48: ZoneHashMap::Entry* p = map->Lookup(name.location(),
name->Hash(), false);
Hash relies on the actual String contents, while Match relies on pointer
identity. Therefore Hash is a bit of overkill, you could hash the pointer value.
But I am not sure how performance-critical this is, so I leave this up to you.

http://codereview.chromium.org/9615009/diff/1/src/interface.cc#newcode169
src/interface.cc:169: this->DoAdd(p->key, p->hash,
static_cast<Interface*>(p->value), ok);
If I see this correctly, this recursion is potentially bounded only by the
structure of the input. Although this won't be a problem in practice, I think we
will have to add a guard against pathological cases (or attacks).

http://codereview.chromium.org/9615009/diff/1/src/interface.h
File src/interface.h (right):

http://codereview.chromium.org/9615009/diff/1/src/interface.h#newcode31
src/interface.h:31: #include "zone-inl.h"
Do we really need a zone-inl.h here or is zone.h enough? Furthermore, a lot of
entities are used in the current header which get only accidentally pulled in by
zone-inl.h, so a bit more IWYU would be nice, making things less fragile.

http://codereview.chromium.org/9615009/diff/1/src/interface.h#newcode40
src/interface.h:40: //   exports ::= {name : interface, [CLOSED]}
Hmmm, according to the code below, VALUEs can be CLOSED, too. Either the comment
or the code is wrong...

http://codereview.chromium.org/9615009/diff/1/src/interface.h#newcode52
src/interface.h:52: static Interface value_interface(VALUE);
Huh? Why is this a singleton?

http://codereview.chromium.org/9615009/diff/1/src/interface.h#newcode122
src/interface.h:122: enum Flags {    // All flags are monotonous
Hmmm, I am not totally happy with that representation. I think what is actually
modeled is something like:

   data Kind = Value | Module;
   data Flexibility = Flexible | Frozen
   data State = Unknown | Known Kind Flexibility

This type has 5 values, your type has 8. It would be nicer if the C stuff would
be closer to the Haskell types above, but I leave it up to you to polish this or
not.

http://codereview.chromium.org/9615009/diff/1/src/scopes.cc
File src/scopes.cc (right):

http://codereview.chromium.org/9615009/diff/1/src/scopes.cc#newcode1033
src/scopes.cc:1033: if (!inner_scopes_[i]->ResolveVariablesRecursively(info,
factory))
I know that this recursive call has been there before, but shouldn't we guard
against pathological cases/attacks here?

http://codereview.chromium.org/9615009/diff/1/test/mjsunit/harmony/module-par...
File test/mjsunit/harmony/module-parsing.js (right):

http://codereview.chromium.org/9615009/diff/1/test/mjsunit/harmony/module-par...
test/mjsunit/harmony/module-parsing.js:30: // Test basic module syntax, with and
without ASI.
What's "ASI"? Asociación Salvadoreña de Industriales? :-)

[rossberg, 2012-03-08 10:47:06]

https://chromiumcodereview.appspot.com/9615009/diff/1/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9615009/diff/1/src/ast.h#newcode614
src/ast.h:614: explicit ModuleLiteral(Block* body, Interface* interface)
On 2012/03/08 08:55:00, Sven Panne wrote:
> Remove "explicit".

Done.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/ast.h#newcode2519
src/ast.h:2519: // Out-of-line inline constructors.
On 2012/03/08 08:55:00, Sven Panne wrote:
> I guess this here for cyclic dependencies reasons, so a remark in the comment
> would be nice.

Done.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.cc
File src/interface.cc (right):

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.cc#newcode48
src/interface.cc:48: ZoneHashMap::Entry* p = map->Lookup(name.location(),
name->Hash(), false);
On 2012/03/08 08:55:00, Sven Panne wrote:
> Hash relies on the actual String contents, while Match relies on pointer
> identity. Therefore Hash is a bit of overkill, you could hash the pointer
value.
> But I am not sure how performance-critical this is, so I leave this up to you.

I pretty much copied this bit from the code in scopes.cc. Also, we might
eventually need to make interfaces persistent across compiles, so view it as a
partial preparation for that. :)

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.cc#newcod...
src/interface.cc:169: this->DoAdd(p->key, p->hash,
static_cast<Interface*>(p->value), ok);
On 2012/03/08 08:55:00, Sven Panne wrote:
> If I see this correctly, this recursion is potentially bounded only by the
> structure of the input. Although this won't be a problem in practice, I think
we
> will have to add a guard against pathological cases (or attacks).

The depth of module types is linearly bounded by the size of the program.
Realistically, it is more likely that the stack is first blown by the parser,
which does not protect against that event either AFAICS. So I don't think it's
currently worth doing here.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.h
File src/interface.h (right):

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.h#newcode31
src/interface.h:31: #include "zone-inl.h"
On 2012/03/08 08:55:00, Sven Panne wrote:
> Do we really need a zone-inl.h here or is zone.h enough? Furthermore, a lot of
> entities are used in the current header which get only accidentally pulled in
by
> zone-inl.h, so a bit more IWYU would be nice, making things less fragile.

It's needed for the use of 'new' below. Added a comment.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.h#newcode40
src/interface.h:40: //   exports ::= {name : interface, [CLOSED]}
On 2012/03/08 08:55:00, Sven Panne wrote:
> Hmmm, according to the code below, VALUEs can be CLOSED, too. Either the
comment
> or the code is wrong...

Yeah, I generalized the semantics of closed/frozen last minute and forgot to
update the comment properly. Done.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.h#newcode52
src/interface.h:52: static Interface value_interface(VALUE);
On 2012/03/08 08:55:00, Sven Panne wrote:
> Huh? Why is this a singleton?

Should be VALUE + FROZEN now.

There is only one such value type, so I "cache" it to avoid reallocation. Added
a comment.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/interface.h#newcode122
src/interface.h:122: enum Flags {    // All flags are monotonous
On 2012/03/08 08:55:00, Sven Panne wrote:
> Hmmm, I am not totally happy with that representation. I think what is
actually
> modeled is something like:
> 
>    data Kind = Value | Module;
>    data Flexibility = Flexible | Frozen
>    data State = Unknown | Known Kind Flexibility
> 
> This type has 5 values, your type has 8. It would be nicer if the C stuff
would
> be closer to the Haskell types above, but I leave it up to you to polish this
or
> not.

What I really want is a lattice where

Unknown < Value < Frozen Value
Unknown < Module < Frozen Module
Value < Module

and efficient checks whether something is below a certain bound. The most
efficient way to do that is with a bit mask, even if that contains some
nonsensical values.

https://chromiumcodereview.appspot.com/9615009/diff/1/src/scopes.cc
File src/scopes.cc (right):

https://chromiumcodereview.appspot.com/9615009/diff/1/src/scopes.cc#newcode1033
src/scopes.cc:1033: if (!inner_scopes_[i]->ResolveVariablesRecursively(info,
factory))
On 2012/03/08 08:55:00, Sven Panne wrote:
> I know that this recursive call has been there before, but shouldn't we guard
> against pathological cases/attacks here?

See my respective comment in interface.cc.

https://chromiumcodereview.appspot.com/9615009/diff/1/test/mjsunit/harmony/mo...
File test/mjsunit/harmony/module-parsing.js (right):

https://chromiumcodereview.appspot.com/9615009/diff/1/test/mjsunit/harmony/mo...
test/mjsunit/harmony/module-parsing.js:30: // Test basic module syntax, with and
without ASI.
On 2012/03/08 08:55:00, Sven Panne wrote:
> What's "ASI"? Asociación Salvadoreña de Industriales? :-)

JS speak for "automatic semicolon insertion". Changed.

[Sven Panne, 2012-03-08 12:12:15]

LGTM, potential stack overflow in unification will be handled in separate CL, as
discussed offline.