Microsoft/TypeScript — pull request #1239 by CyrusNajmabadi (2014-11-22 00:18:00+00:00)
Title: Change how the incremental parser works.

Previously the incremental parser worked in a mode where it would reuse nodes prior to the editedrange, then skip over nodes/tokens in the edited range, then reuse nodes after the edit range. The reused nodes after the edit range would then have to have their positions fixed up. i.e. they might move forward/backward depending on what sort of edit it was.

This approach resulted in extra complexity as the incremental parser had to keep track of where it was, and how the position it was in the tree related to the position it was at in the text. This involved keeping track of two different positions in two different sources (the old tree and the text) and keep a relative 'delta' between then to tell if they were in sync.

Thanks to a suggestion from bill, i've moved things to a simpler model that makes things only slightly more expensive. Specifically, we start the incremental parse with a prepass over the tree. We skip over all nodes quickly that fall totally before the edit range. Then we mark all nodes and tokens in the edit range as being unusable. Then we move all tokens that fall totally after the change range forward.

Thanks to this, all nodes/tokens from the old tree that we look at are either marked as unusable, or are located at the same position they would be at in the new text. This means we no longer need to keep track of relative positions between two sources. Instead, we can simply try move to the node that matches the current text position. If we find one, we can return it. Otherwise, we know we need to keep rescanning tokens from the new text.