Multi-pass traversal

[getify]

To account for function hoisting and recursion, as well as the fact that TypVal lazily discovers types through runtime mechanisms like first assignment or call-site, we'll need a multi-pass traversal.

Alternately, if we had a way to do two traversals, one forward and one reverse (both still depth-first, but reversing the order of any sibling iteration), we would only need (at most) those two passes. But I'm not sure if that kind of traversal is possible. So for now, going to assume we will need the multi-pass traversal as described below.

Errors from each pass are thrown away once the next pass is started, so that only errors from the final pass will be reported. The problem is, it's impossible to predict how many passes are needed, because of pathological scenarios like this:

// ..
function e() { return d(); }
function d() { return c(); }
function c() { return b(); }
function b() { return a(); }
function a() { return 1; }

In this example, the first pass registers the type signature for a, but only after b(), c(), d(), and e() were already processed, meaning they all are in an "unknown" return-type state. A second pass (now knowing the return of a()) will register the type signature for b(). A third pass handles c(), etc. It would take 5 passes to get all type signatures correct here.

Another example of the call-site typing issue requiring multiple passes involves recursion:

function a(x) {
   if (x > 1) return 3 + a(x - 1);
   return "X";
}
a(11);  // "3333333333X"

We can't validate the + operator expression on the first pass because we don't yet know the non-recursive return type of the function a(..), which we only discover on the first pass, and we need then a second pass to validate the + expression (in this case, would display an error about the type mismatch of number and string).

So how can we tell during one pass that we'll need one or more passes to handle these kind issues?

On each pass, start with two empty Sets "A" and "B". Every time we encounter an identifier (anywhere) in an RHS position, or a call-site, and we don't yet know its type, add the scope-binding of that identifier or the type-signature of the function to the "A" set.

Any time we infer or tag the type of an identifier (via some assignment) or function return value (via return ..) that was previously unknown, add scope-binding of that identifier or the type-signature of the function to the "B" set.

At the end, iterate over all the items in "A"; if any item is also in "B", then we need another pass. If not, there's nothing left to gain from another pass, so we can stop.

We might want to set a max limit (configurable of course, maybe default to 5?) on number of passes, and issue a warning/error if we hit the limit with any indication that more passes were needed but not performed.

---

Each pass of the full traversal will do these steps:

1. increment a global counter for the pass-index

2. set an empty list of errors

3. for each inferred/tagged type, set a passIndex: {number} property.

4. track items for sets "A" and "B", as described above.

5. for any assignment, if the binding already has a type, but its passIndex is less than the current pass-index, just overwrite the binding's type and update the passIndex.

   but if an assignment occurs to a binding's type where the passIndex is current, that means it's a subsequent assignment in a program that should be validated (and any errors collected).

6. at the end of traversal, compare sets "A" and "B", as described above.

   if another pass is needed, check against the max-limit. if it's exceeded, throw an error/warning and stop. otherwise, repeat another pass starting at step 1.

7. after we're done with passes, report any errors that were collected in that last pass.