Incremental compiler

Topics: Code Checkins
May 30, 2014 at 10:02 AM
Would you guys kindly spare few minutes briefing the community about incremental compilation that keeps being mentioned in the commits on develop branch?

I assume that is the reason you leave VS2012 behind and focus on VS2013?

I'm guessing you want to boost the performance of the parser to enable more structural understanding of the code in the editor, and adding all those fancy in-place callouts with tests, references and other hints, right?

Please don't reply with yes/no, give us some meat here :-)
Developer
May 30, 2014 at 11:58 PM
Edited May 31, 2014 at 12:17 AM
Hey there,

Could you be more specific? Which checkins are you referring to? Thanks!
Jun 2, 2014 at 10:57 AM
When I open the history page and Ctrl+F for 'incremental', I find commits by one Cyrus Najmabadi. Perhaps you might ask him to be more specific? ;-)

Inceremental parsing, right? What is it, how one can invoke it from services?
Jun 2, 2014 at 11:03 AM
https://typescript.codeplex.com/SourceControl/changeset/9998ee3808caba5bd6730cb5600ed2ca4f7782a2
throw an exception if someone tries to incrementally parse an abstract syntax tree.

https://typescript.codeplex.com/SourceControl/changeset/584f39e10c4962e11156d66f717ca0bc03891e22
Revert "Allow incremental parsing to work in more situations."
This reverts commit 9f5faddb3a88ce6cda98b354ec35338665ad85a3.
There were still some sitations where parent pointers were wrong. I've added more aggressive checks
in the test harness to catch this, and i've reverted this optimization. We now incrementally parse
as before. i.e. if we're speculatively parsing, we don't reuse nodes from the old tree.

https://typescript.codeplex.com/SourceControl/changeset/9f5faddb3a88ce6cda98b354ec35338665ad85a3
Allow incremental parsing to work in more situations.
Previously, we restricted incremental parsing so that it wouldn't apply during speculative
scenarios (like when trying to determine if < was part of a generic type argument list, or just an
arithmetic operator). This was due to how the parser updated nodes and tokens, and how that could
throw off the incremental parser. Because of that, hte incremental parser would effectively shut
itself off in speculative scenarios. Now, we properly handle speculative parsing, and can reuse
far more nodes. It also means less abstraction leakage betweeen the incremental parser and the
underlying scanner it sometimes needs to defer to.

https://typescript.codeplex.com/SourceControl/changeset/7884875f2bd32363318a6ead4155283028f23ef4
Update comment to make incremental parser rules clearer.

https://typescript.codeplex.com/SourceControl/changeset/08f3dc079276db78a7faab82ec7936e1e55325fd
Add incremental tests.

https://typescript.codeplex.com/SourceControl/changeset/161342a8851849cd828744c7e495b9c601faeea9
Adding incremental test.

https://typescript.codeplex.com/SourceControl/changeset/18daa4380c90039c36a6d0c3283aaeab5df7b570
Adding some incremental parser tests.

https://typescript.codeplex.com/SourceControl/changeset/0665ea51ecb4e70b55e56c836c168101a2f49200
Move the incremental parser almost entirely over to functions instead of classes.
Jun 2, 2014 at 11:10 AM
Looks like pretty significant piece of functionality someone is working on. By the amount of design changes and refactorings, it looks like that stuff is not entirely agreed upon by some of the 'architecty' chiefs. Imagine working under Anders might be tough at times.
Developer
Jun 2, 2014 at 5:39 PM
Edited Jun 2, 2014 at 5:46 PM
Hi Mihailik,

"Inceremental parsing, right? What is it, "

Incremental parsing is the functionality we have for more efficiently producing a syntax tree after a text change if we already parsed a tree prior to the change. i.e. instead of needing to parse the entire file again, we can essentially (and i'm vastly oversimplifying here) only reparse the parts of the file that have changed.

"how one can invoke it from services?"

Incremental parsing is already invoked from the services layer as necessary. For example, say a request for brace matching comes in. The first thing the services layer will do is see if there have been any text changes on the host side. If so, it will take in those changes and incrementally parse if it can. This allows it to answer the brace matching question faster than if it had to do a full parse.

I hope that helps explain things.
Developer
Jun 2, 2014 at 5:40 PM
"throw an exception if someone tries to incrementally parse an abstract syntax tree. "

Incremental parsing only works when we have a concrete syntax tree and not an abstract syntax tree (i.e. a lossy tree). We want to throw in that case to let someone know if they're doing something they should not be doing.
Developer
Jun 2, 2014 at 5:42 PM
"Revert "Allow incremental parsing to work in more situations."
This reverts commit 9f5faddb3a88ce6cda98b354ec35338665ad85a3.
There were still some sitations where parent pointers were wrong."

I previously put in an optimization to allow us to incrementally parse in more situations (including in the parts of the parse where were 'speculatively' parsing to figure out what sort of construct we have). However, the optimization wasn't completely correct.

A necessary invariant of incremental parsing is that it must produce the same results as a regular parse. If it is not maintaining that invariant, then that is a bug that must be addressed. In this case, post my optimization, it was the case that you could end up with a syntax tree where some tokens had parents pointing to nodes not in the tree. That's obviously bad. So i reverted the work until the point that i can actually produce an algorithm that doesn't have that problem.
Developer
Jun 2, 2014 at 5:46 PM
Edited Jun 2, 2014 at 5:47 PM
The next batch of changes are all around incremental parser tests. I just want our test bed to be strong so that it catches any issues as refactorings occur.

"Move the incremental parser almost entirely over to functions instead of classes."

This change is around a new style of coding that we're investigating. Because JavaScript is routinely written with Functions+Nested-Functions+Function Captures, i wanted to see what it would be like to use such patterns on a significant piece of code. This helps inform us of how best to move our own features (like Language Services) forward now that we can have some code that more accurately represents the type of code you might see in the JavaScript community.

If there are any other questions you have, please don't hesitate to ask!
  • Cyrus
Jun 2, 2014 at 5:51 PM
Pretty decent and clear explanation, great thanks Cyrus! Very helpful indeed.