Add a way to get a typed AST

[eatonphil]

I am working on a JS to C compiler using Esprima to get the AST. I started out actually targeting C++11 and was able to get by using the auto keyword when I didn't know a type. This is a hassle and I really want to target ANSI C. It would be excellent if Flow could export the typed AST. Is this currently possible?

[gabelevi]

If all you needed was the AST with the explicit type annotations then you could use the Flow parser or the esprima-fb fork, but I'm guessing what you need is the AST with all the inferred types, right? This isn't something that is currently available, but I think it would be doable to produce.

The way Flow works is by visiting the AST and linking things together by flow types to other types. For example, when it sees var x = 123 it creates a type variable for x and then flows a number type to that type variable. In the process of processing these flows, it might create even more flows (like calling a function creates flows from the call arguments to the function parameters). So while we start off by operating on the AST, we're pretty soon just operating on these flows.

However, we should have type variables for each local variable, function parameter, etc., so I imagine we could always annotate our AST with these inferred types by looking up what the type variables resolved to. We've been keeping this in the back of our mind because we'd love to run transformers, linters, etc. on JS ASTs with type information available.

What we do currently have is flow type-at-pos file.js 12 3 which queries for the type of the thing in file.js at line 12 column 3. This is what the vim plugin asks for when you do :FlowType. It's not perfect...sometimes it gives up when it doesn't know how to pretty print an inferred type, but it is helpful and it does exist right now.

[junosuarez]

Inferred types on AST nodes is very useful for a whole host of other tooling. Incremental parsing and type inference, such as offered by the TypeScript tsc services, is even better for editor-time tooling.

[dead-claudia]

Not to mention a typed AST would make compilers much more efficient. A minifier that knows how to deal with types can both make far smaller code and far faster code. I could see the results of this potentially enabling a JavaScript to (gasp) native compiler as well.

This always gets me imagining a 100% self-hosted JavaScript VM. Or a JavaScript to C/C++ bridge that can be settled at compile time. Or even a browser mostly self-hosted in JavaScript. Or something like Runtime.JS, but without the need for hardly any C/C++ in it. Or, a JS compiler that intelligently knows when it can write asm.js, and when it cannot, and how to duplicate methods for maximum speed, giving several more fast paths than just what's hardcoded.

But I digress...it would unlock a lot of potential, though. IDEs aren't the only ones that would easily benefit.

[gabelevi]

It's a little bit tricky to build a sound type system on top of JavaScript, and an unsound typed AST might be a little bit of a problem for a compiler. Andreas Rossberg is experimenting with a subset of JavaScript with slightly different semantics. It's an interesting proposal!

[jeffmo]

Definitely something we want to explore in the long run. @gabelevi mentioned the fact that soundness does limit the use-cases a bit. As just one example:

myVar.forEach(function(item) {
  this.doStuff(item);
}.bind(this));

If you're confident that myVar is actually an array, you might make this code slightly more efficient by changing it to

myVar.forEach(function(item) {
  this.doStuff(item);
}, this);

(bound functions are slower in many JS engines)

However, if you're not 100% sure that myVar is of the native array type, doing this optimization is not safe! For example, there are plenty of libraries out there with a .forEach() method that doesn't take a second "context" argument.

So soundness will be important to pretty much all of these kinds of minification and optimization strategies. But even if we move past soundness, there's a second class of information you might want to take advantage of that doesn't quite fit neatly into a syntax tree -- which is that of type relations like subtyping.

For example, in my previous scenario, we can make that optimization if myVar is a native array type -- or if it's a subtype of the native array type (whose .forEach method is either the same or compatible). So answering these kinds of questions is also of interest for doing any more extensive work with type information.

Anyway -- great to hear others are as interested in this as we are. Hopefully as we get the type system a little more stabilized we can start focusing on things like this a little more.

[dead-claudia]

Bump: this would be extremely helpful for babel/babel#653. Hopefully, some progress could be made on this?

[jeffmo]

cc @mroch

[ozra]

This would be so useful. I've played around alot with DSLing and toying with transpilings since 1999. I've been thinking it's better to use an 'external established' de-facto JS type system, rather than rolling a bunch, because of lib-interfaces etc. + Flow seems so damn good. Thereby doing two-step transpiling. The (inferred) typed AST would be helpful in many ways for DSL post-manipulations where types would make targeting the right nodes for mutations razor sharp. Also, as mentioned earlier, the type info could be used to figure out when it's reasonable to generate asm.js output or just POJS. Type aliases must then be in AST, so the type is not "reduced", since not number, but double, float and int, is native-compilable by asm.js aware engines

I don't know enough about type theory or the implementation to understand fully what cannot be fit in an AST, but, I can't imagine why it wouldn't be possible to express the type magic structurally somewhere in an AST? Would it take up to much space?

[ozra]

While I'm at it, here's a concrete example of what I'd like to do (semi pseudo - untested code):

class Foo {
    constructor() {    
        this.vals = [42, 47];
    }
    _subscript_(i : int) {
        return this.vals[this.vals.length - 1 - i]; 
    }
    _subscript_set_(i : int, v: int) {
        this.vals[this.vals.length - 1 - i] = v; 
    }

var a : Foo = new Foo()
foo[0];   // => 47
foo.vals[0];   // => 42
foo[1] = 13;   // void
foo.vals[0];   // => 13

That is, by traversing the AST and seeing a subscript access on a variable of type class with _subscript_ defined, I could replace the subscript with a call to the method.

I have a completely different syntax for the small lang which compiles to JS, with the above I could leverage operator overloading which would be a great help in my specific application, compiled to above names for instance (mangled a bit more...) If I'd transpile to Flow instead of JS, and could access the types in AST..

weird-DSL-lang => Flow => AST-mutation => JavaScript

[dead-claudia]

By the way, there are still interested users in babel/babel#653. I also see uses in other areas as well.

[leeola]

This would be great! I'd kill to see/make a flowfmt akin to gofmt. (perhaps that is possible with Babel's AST?)

[jsommr]

Any news? Would be cool to build documentation from a Flow AST.

[PatoBeltran]

Any update on this? It would be awesome to get some typed AST, it would bring a whole lot of new possibilities to flow.

[jamiebuilds]

There is interest in doing this along with other tools for exposing information from Flow. We will be sure to update the issue once we have something.

[jslegers]

Or, a JS compiler that intelligently knows when it can write asm.js, and when it cannot, and how to duplicate methods for maximum speed, giving several more fast paths than just what's hardcoded.

That's precisely what I've been looking for today. IMO, the main benefit of adding static typing is the ability to optimize for that, especially through compilation to asm.js whenever your code is sufficiently similar to C++-code to allow it. I'm sure you can imagine my surprise and frustration finding out that neither the TypeScript devs nor the Flow devs appear to be interested in implementing this totally game changing feature.

I guess being able to export the AST with the explicit type annotations would be a first step, however, for other developers to implement compilation or Flow/JavaScript to asm.js... by first passing through C++ or otherwise...

Anyway, I guess this issue is related to issue #570?

[jslegers]

As I see it, the ability to export a language like Flow or TypeScript to typed AST in some way or another would allow another team of developers to use that as a basis for "TypeScript to C/C++", "TypeScript to asm.js" or "TypeScript to whatever" conversions.

The short term benefit would obviously be small, but the large term benefit would be quite significant, as it would basically provide a pluggable interface that allows (subsets of?) Flow to be converted to any language that is sufficiently compatible. In theory, it would allow Flow - when combined with third party plug-ins" - to be used as some kind of "convert to anything" kind of language, which is what many people are trying to use JavaScript for but for which JavaScript (due to the lack of static typing) happens to be less suitable than Flow or TypeScript. And this, with - I imagine - little effort from the Flow core devs, as exporting the typed AST that is used internally would be all they would have to do to make this possible.

[magicmark]

Is it reasonable for this to be implemented as a babel plugin? Or is it better just to leverage the existing type hinting system in the flow engine?

I was also wanting this, so I did some weekend side-project hackery...

https://github.com/magicmark/babel-plugin-transform-flow-untyped (wip)

@jeffmo @gabelevi Is this a terrible idea? (This is my first real experience with babel plugins/ASTs, I don't know much about flow internals, so I'm genuinely curious)

Thanks!

[rattrayalex]

@magicmark tl;dr, no, that wouldn't do it. Babel's type inference is but a butterfly in the wind to the fighter jet that is Flow.

[jamiebuilds]

Babel would actually be a really good place to have this. Extracting Flow types into a Babylon AST would be hugely useful for a lot of tools. It should be querying Flow for type information, but it's not a bad idea.

[rattrayalex]

Ah, I thought he meant a babel plugin that would do the inference itself. A babel plugin that queries flow for information on each node does sound great!

However, doing so node-at-a-time for each node would be slow – which is why this issue was opened in the first place, afaict.

A helper function to the effect of getFlowTypeForNode which looks at the source location for the node, sends a request to the flow server for type information at that location, and synchronously returns the result certainly sounds useful and feasible.

@thejameskyle is that what you had in mind?

[jamiebuilds]

Yeah, I've tried to build that in the past using the CLI but at the time Flow had a lot of problems getting a type for every source location.

[insuyun]

Any update on this?

[pakoito]

Hello y'all! We have had a typed AST for several months now, alongside mappers and helpers to work on it.

If anyone in the community would be seriously interested in consuming said TAST, we can have some VC chat about it.

[goodmind]

@pakoito is it public api?

[pakoito]

Yes, you can find the helpers in the repo today and it's represented as one of the polymorphic fields on the AST. We'd need to discuss how to expose them to be consumed by other tools, which is why it'd be better for anyone interested to contact us directly with a good proposal :D

[phpnode]

@pakoito we can currently run flow ast file.js to produce a babylon compatible AST, it would be great if we could run flow infer-ast file.js to produce a similarly compatible AST with all inferred type annotations attached to their relevant nodes.

[pakoito]

The TAST could be considered a superset of Babylon AST. The types exposed are not the ones in regular type annotations, but the ones defined in ty.ml, and are only attached to some nodes (look for 'T * here).

Knowing that, we'd need to work on porting those types and extending the Babylon AST in a principled way, which we have not sat down to design yet (roadmap yay!). If a partner would like to step in to collaborate on it to have the spec ready, we could speed up the process and work on the porting/exposing side.

[goodmind]

@pakoito Can't they be mapped to regular type annotations AST nodes from babel so it is seamless transition?

[pakoito]

You lose all interesting information about provenance, structure, kind...you'd basically lose everything that makes a TAST relevant. What you want is possible (albeit cumbersome) today with type-at-pos AFAIK.

[rattrayalex]

Fwiw, type-at-pos for every node in the file is all I think I wanted.

Providing the richer information sounds good too, perhaps in a separate field (flowType and flowInternalType, maybe).

Even as an educational tool, this could be useful for people to learn how flow sees a program, if a UI is added to the try flow website

[goodmind]

@pakoito how this can move forward? Can we just get same JSON AST for this?

[pakoito]

I am no longer in the Flow team, @panagosg7 may have more info!