robey/packrattle — pull request #4 by hallettj (2013-05-29 02:13:59+00:00)
Title: Uses WeakMap to resolve each parser exactly once

As I said in my previous pull request, I have found packrattle's ability to lazily evaluate parsers to be quite helpful. I am finding that the simplest way to avoid worrying about having to define parsers in a particular order is create every parser as a function that returns a parser. Except that I ended up with some nonterminating recursion due to each reference to a parser invoking its wrapping function anew.

It looks like you made some effort to emulate Scala's lazy val feature. That seems like a good idea to me. From what I understand when a lazy val in Scala is forced its value is memoized so that subsequent references do not re-evaluate the val's thunk. I thought that packrattle could get closer to Scala's behavior by storing resolved parsers in a lazy cache.

This change maintains an internal weak map with entries for every parser that is resolved by invoking a function. This means that any parsers that are defined as functions are resolved exactly once. For example:

expression = ->
$.alt(
/\d+/,
$.seq(expression, '+', expression)
)

The toplevel and recursive references to expression will resolve to the same object.

The lazy cache is implemented as a weak map that uses functions as keys to look up resolved parsers. Because it is a weak map if the function that defines a parser is garbage-collected then the corresponding map entry will also be garbage collected.

Node has a native implementation of [WeakMap][] as described in the ECMAScript 6 draft spec, which implements true weak references - but that implementation is only enabled if Node is run with the `--harmony_collections` or `--harmony` flags. The [weakmap][polyfill] package that I used in this changeset provides a fallback implementation that stores map values in non-enumerable properties on the corresponding map keys.

[WeakMap]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakMap
[polyfill]: http://benvie.github.io/WeakMap/